Solution
Approach #1: Principle of InclusionExclusion
Intuition
Say we have two rectangles, and . The area of their union is:
Say we have three rectangles, . The area of their union is:
This can be seen by drawing a Venn diagram.
Say we have four rectangles, . The area of their union is:
In general, the area of the union of rectangles will be:
Algorithm
If we do not know the above fact, we can prove it by considering any point in . Say this point occurs in all , and let . Then on the right side, it is counted times. By considering the binomial expansion of , this is in fact equal to .
From Rectangle Area I, we know that the intersection of two axisaligned rectangles is another axisaligned rectangle (or nothing). So in particular, the intersection is always a rectangle (or nothing).
Now our algorithm proceeds as follows: for every subset of (where is the number of rectangles), we'll calculate the intersection of the rectangles in that subset , and then the area of that rectangle. This allows us to calculate algorithmically the righthand side of the general equation we wrote earlier.
Complexity Analysis

Time Complexity: , where is the number of rectangles.

Space Complexity: .
Approach #2: Coordinate Compression
Intuition
Suppose instead of rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
, we had [[0,0,200,200],[100,0,200,300],[100,0,300,100]]
. The answer would just be 100 times bigger.
What about if rectangles = [[0,0,2,2],[1,0,2,3],[1,0,30002,1]]
? Only the blue region would have area 30000
instead of 1
.
Our idea is this: we'll take all the x
and y
coordinates, and remap them to 0, 1, 2, ...
etc. For example, if rectangles = [[0,0,200,200],[100,0,200,300],[100,0,300,100]]
, we could remap it to [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
. Then, we can solve the problem with brute force. However, each region may actually represent some larger area, so we'll need to adjust for that at the end.
Algorithm
Remap each x
coordinate to 0, 1, 2, ...
. Independently, remap all y
coordinates too.
We then have a problem that can be solved by brute force: for each rectangle with remapped coordinates (rx1, ry1, rx2, ry2)
, we can fill the grid grid[x][y] = True
for rx1 <= x < rx2
and ry1 <= y < ry2
.
Afterwards, each grid[rx][ry]
represents the area (imapx(rx+1)  imapx(rx)) * (imapy(ry+1)  imapy(ry))
, where if x
got remapped to rx
, then imapx(rx) = x
("inversemapx of remappedx equals x"), and similarly for imapy
.
Complexity Analysis

Time Complexity: , where is the number of rectangles.

Space Complexity: .
Approach #3: Line Sweep
Intuition
Imagine we pass a horizontal line from bottom to top over the shape. We have some active intervals on this horizontal line, which gets updated twice for each rectangle. In total, there are events, and we can update our (up to ) active horizontal intervals for each update.
Algorithm
For a rectangle like rec = [1,0,3,1]
, the first update is to add [1, 3]
to the active set at y = 0
, and the second update is to remove [1, 3]
at y = 1
. Note that adding and removing respects multiplicity  if we also added [0, 2]
at y = 0
, then removing [1, 3]
at y = 1
will still leave us with [0, 2]
active.
This gives us a plan: create these two events for each rectangle, then process all the events in sorted order of y
. The issue now is deciding how to process the events add(x1, x2)
and remove(x1, x2)
such that we are able to query()
the total horizontal length of our active intervals.
We can use the fact that our remove(...)
operation will always be on an interval that was previously added. Let's store all the (x1, x2)
intervals in sorted order. Then, we can query()
in linear time using a technique similar to a classic LeetCode problem, Merge Intervals.
Complexity Analysis

Time Complexity: , where is the number of rectangles.

Space Complexity: .
Approach #4: Segment Tree
Intuition and Algorithm
As in Approach #3, we want to support add(x1, x2)
, remove(x1, x2)
, and query()
. While outside the scope of a typical interview, this is the perfect setting for using a segment tree. For completeness, we include the following implementation.
You can learn more about Segment Trees by visiting the articles of these problems: Falling Squares, Number of Longest Increasing Subsequence.
Complexity Analysis

Time Complexity: , where is the number of rectangles.

Space Complexity: .
Analysis written by: @awice. Idea for Solution #4 by @lee215.