Problem statement

https://leetcode.com/problems/rectangle-area-ii/

Solution 1

One of the approaches is to do coordinates compression: for every 2n x and y coordinates, there is in total will be O(n^2) possible candidates for part of figure. Then we can find for each of these candidates in O(n) if it is part of figure or not.

Complexity

Time complexity will be O(n^3), space is O(n^2) or can be done in O(n) as well.

Code

class Solution:
    def rectangleArea(self, rectangles):
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        ys = sorted(set([y for x1, y1, x2, y2 in rectangles for y in [y1, y2]]))
        x_i = {v: i for i, v in enumerate(xs)}
        y_i = {v: i for i, v in enumerate(ys)}
        m, n = len(y_i), len(x_i)
        
        grid = [[0] * m for _ in range(n)]
        for x1, y1, x2, y2 in rectangles:
            for x in range(x_i[x1], x_i[x2]):
                for y in range(y_i[y1], y_i[y2]):
                    grid[x][y] = 1

        ans = 0
        for x in range(n-1):
            for y in range(m-1):
                ans += grid[x][y]*(xs[x+1] - xs[x]) * (ys[y+1] - ys[y])
        return ans  % (10**9 + 7)

Solution 2

There is another solution, using line sweep. Let us sort our rectangles by x coordinate and move vertical line from left to right. Then we can use problem 56. Merge Intervals: we need to keep active set of sides and then remove them or add to it. Also we can use neat trick to handle sides from different rectangles which have the same x coordinate, using value prev_x.

Complexity

Time complexity will be O(n^2 log n), space complexity is O(n).

Code

class Solution:
    def rectangleArea(self, rectangles):
        def merge(intervals):
            ans = []
            for beg, end in sorted(intervals):
                if not ans or ans[-1][1] < beg:
                    ans += [[beg, end]]
                else:
                    ans[-1][1] = max(ans[-1][1], end)
            return sum(j-i for i,j in ans)
        
        sides_lft = [(x1,0,y1,y2) for x1,y1,x2,y2 in rectangles]
        sides_rgh = [(x2,1,y1,y2) for x1,y1,x2,y2 in rectangles]
        sides = sorted(sides_lft + sides_rgh)
        
        intervals, ans, prev_x = [], 0, sides[0][0]

        for x, op_cl, y1, y2 in sides:
            ans += merge(intervals) * (x - prev_x)
            
            if op_cl == 0:
                intervals.append((y1,y2))
            else:
                intervals.remove((y1,y2))     
            prev_x = x
            
        return ans % (10**9 + 7)

Solution 3

Actually, we can do our interval merge in O(n) time instead of O(n^2). First, let us create all unique y coordinates: set ys, then we create correspondences between indexes and these y coordinates: this is y_i dictionary. Finally, count will be count: how many times each segment is covered. We again create sides like in previous approach.

Next, we again iterate through our sides and update area, but now when we meet new segment, we update count} for range: +1 for start of rectangle and -1 for end of rectangle. Finally, we update our cur_y_sum: we check if count is 0 and if it is more than 0, we add length of this segment to cur_y_sum.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def rectangleArea(self, rectangles):
        ys = sorted(set([y for x1, y1, x2, y2 in rectangles for y in [y1, y2]]))
        y_i = {v: i for i, v in enumerate(ys)}
        count = [0] * len(y_i)
        
        sides_lft = [(x1,-1,y1,y2) for x1,y1,x2,y2 in rectangles]
        sides_rgh = [(x2,1,y1,y2) for x1,y1,x2,y2 in rectangles]
        sides = sorted(sides_lft + sides_rgh)
         
        cur_x = cur_y_sum = area = 0
        for x, op_cl, y1, y2 in sides:
            area += (x - cur_x) * cur_y_sum
            cur_x = x
            for i in range(y_i[y1], y_i[y2]):
                count[i] += op_cl
            cur_y_sum = sum(y2 - y1 if c else 0 for y1, y2, c in zip(ys, ys[1:], count))
        return area % (10 ** 9 + 7)

Solution 4

There is also O(n log n) solution, using segment trees. The idea is to use segment tree where we need to deal only with updates of ranges. If we need only range updats, and not queries, not need to do lazy updates - see https://cp-algorithms.com/data_structures/segment_tree.html, (Addition on segments) chapter. Also we need to need to keep self.total dictionary, which for each segment will calculate lenght of all active segments we have so far.

Complexity

It is just O(n log n).

Code

class SegmentTree:
    def __init__(self, xs):
        self.cnts = defaultdict(int)
        self.total = defaultdict(int)
        self.xs = xs

    def update(self, v, tl, tr, l, r, h):
        if l > r: return
        if l == tl and r == tr:
            self.cnts[v] += h
        else:
            tm = (tl + tr)//2
            self.update(v*2, tl, tm, l, min(r, tm), h)
            self.update(v*2+1, tm+1, tr, max(l, tm+1), r, h)
          
        if self.cnts[v] > 0:
            self.total[v] = self.xs[tr + 1] - self.xs[tl]
        else:
            self.total[v] = self.total[v*2] + self.total[v*2+1]
        return self.total[v]
    
class Solution:
    def rectangleArea(self, rectangles):
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        xs_i = {x:i for i, x in enumerate(xs)}

        STree = SegmentTree(xs)
        L = []
        for x1, y1, x2, y2 in rectangles:
            L.append([y1, 1, x1, x2])
            L.append([y2, -1, x1, x2])
        L.sort()

        cur_y = cur_x_sum = area = 0
        
        for y, op_cl, x1, x2 in L:
            area += (y - cur_y) * cur_x_sum
            cur_y = y
            STree.update(1, 0,  len(xs) - 1, xs_i[x1], xs_i[x2]-1, op_cl)
            cur_x_sum = STree.total[1]
            
        return area % (10 ** 9 + 7)