Leetcode 850. Rectangle Area II

Problem Explanation

The problem requires finding the total area covered by all rectangles whose coordinates are given. The coordinates represent the bottom-left and the top-right corner of each rectangle. It is important to note that the rectangles could overlap, and in such cases, the overlapping area should not be counted twice. Return the answer modulo 10^9 + 7 because the area covered may be very large.

For example, given the following rectangles:[[0,0,2,2],[1,0,2,3],[1,0,3,1]], the total area covered is 6. This is because the first rectangle covers an area of 4, the second one covers an area of 3, and the third one covers an area of 2. However, since the second and the third rectangle overlap covering an area of 1 and the first and the second rectangle also overlap covering an area of 2, these overlapping areas should only be counted once. Thus the total area covered by all rectangles is 4+3+2-(1 + 2) =6.

Solution Approach

The solution uses a line sweep algorithm. The line sweep algorithm is a computational geometry algorithm that uses a conceptual sweep line that moves across the plane to solve various problems. Here, it is used to replicate drawing the rectangles from left to right.

Each rectangle adds two events - a "start" event when the most left side is first encountered and an "end" event when the most right side is hit. These events are sorted by their x-coordinate, forming a queue.

Then, the events are traversed. The area combined between each pair of events is calculated. If the event is a "start" event, its y1 and y2 are added to vector yPairs; if it is an "end" event, the pair y1 and y2 is removed from vector yPairs. The height of the overlapped area is calculated using function getHeight that iterates through yPairs. Finally, the total combined area is returned as the result.

Python Solution

1
2python
3class Solution:
4    def rectangleArea(self, rectangles):
5        # Create a list of boundaries and events
6        events = []
7        for x1, y1, x2, y2 in rectangles:
8            # append start events and end events
9            events.append((x1, y1, y2, 1)) 
10            events.append((x2, y1, y2, -1))
11        # Sort the events by x coordinate
12        events.sort()
13
14        # Define a function to calculate covered y range
15        def calcY():
16            # If there is no active y range, return 0
17            if not active: return 0
18            # Calculate the covered y range
19            return active[-1][1] - active[0][0]
20
21        area = 0
22        active = []
23        cur_x = events[0][0]
24        for x, y1, y2, t in events:
25            # Calculate the area covered since last x coordinate
26            area += calcY() * (x - cur_x)
27            area %= 10**9 + 7
28
29            # update cur_x
30            cur_x = x
31
32            # Update active intervals
33            i = bisect.bisect_left(active, (y1, float('inf')))
34            j = bisect.bisect_left(active, (y2, float('inf')))
35            # If it is start event, add a new active y range
36            # If it is end event, remove the active y range
37            active[i:j] = [] if t == -1 else [(y1, y2)]
38
39        return area

Java Solution

1
2java
3public class Solution {
4    public int rectangleArea(int[][] rectangles) {
5        int N = rectangles.length;
6        Event[] events = new Event[N*2];
7        int t = 0;
8        for (int[] rec: rectangles) {
9            events[t++] = new Event(rec[1], rec[0], rec[2], true);
10            events[t++] = new Event(rec[3], rec[0], rec[2], false);
11        }
12
13        Arrays.sort(events, new Comparator<Event>() {
14            public int compare(Event a, Event b) {
15                if (a.time != b.time) return a.time - b.time;
16                return a.isStart ? -1 : 1;
17            }
18        });
19
20        List<Interval> active = new ArrayList();
21        long ans = 0;
22        long cur_y = events[0].time;
23        for (Event event: events) {
24            long y = event.time;
25            if (y > cur_y) {
26                ans += calculateInterval(active) * (y - cur_y);
27                ans %= 1_000_000_007;
28                cur_y = y;
29            }
30
31            int idx = Collections.binarySearch(active, new Interval(event.start, event.end));
32            if (event.isStart) {
33                if (idx < 0) idx = ~idx;
34                active.add(idx, new Interval(event.start, event.end));
35            } else {
36                active.remove(idx);
37            }
38        }
39
40        return (int) ans;
41    }
42
43    public long calculateInterval(List<Interval> intervals) {
44        int N = intervals.size();
45        long ans = 0, cur = -1;
46        for (Interval interval: intervals) {
47            cur = Math.max(cur, interval.start);
48            ans += Math.max(interval.end - cur, 0);
49            cur = Math.max(cur, interval.end);
50        }
51        return ans;
52    }
53
54    class Interval implements Comparable<Interval> {
55        int start, end;
56        Interval(int start, int end) {
57            this.start = start;
58            this.end = end;
59        }
60
61        public int compareTo(Interval that) {
62            if (this.start != that.start) return this.start - that.start;
63            else return this.end - that.end;
64        }
65    }
66
67    class Event {
68        int time, start, end;
69        boolean isStart;
70        Event(int t, int s, int e, boolean isS) {
71            time = t;
72            start = s;
73            end = e;
74            isStart = isS;
75        }
76    }
77}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int rectangleArea(vector<vector<int>>& rectangles) {
6        int mod = pow(10, 9) + 7;
7        vector<pair<int, pair<int, int>>> vp;
8        for(auto r : rectangles)
9        {
10            vp.push_back({r[0], {r[1], -r[3]}});
11            vp.push_back({r[2], {r[1], r[3]}});
12        }
13        sort(vp.begin(), vp.end());
14        multiset<pair<int, int>> ms;
15        long area = 0, length = 0;
16        for(int i = 0; i < vp.size(); i++)
17        {
18            if(i > 0)
19                area = (area + ((vp[i].first - vp[i - 1].first) * length)) % mod;
20            if(vp[i].second.second < 0)
21                ms.insert({vp[i].second.first, -vp[i].second.second});
22            else
23            {
24                ms.erase(ms.find({vp[i].second.first, vp[i].second.second}));
25            }
26            length = 0;
27            if(!ms.empty())
28            {
29                auto it = ms.begin();
30                int start = it -> first, end = it -> second;
31                while(it != ms.end())
32                {
33                    start = max(start, it -> first);
34                    end = max(end, it -> second);
35                    if(it -> first > end)
36                    {
37                        length += end - start;
38                        start = it -> first;
39                        end = it -> second;
40                    }
41                    it++;
42                }
43                length += end - start;
44            }
45        }
46        return area;
47    }
48};

C# Solution

1
2csharp
3public class Solution {
4    public int RectangleArea(int[][] rectangles) {
5        int mod = (int)Math.Pow(10, 9) + 7;
6        var list = new List<double[]>();
7        foreach (var rec in rectangles) {
8            list.Add(new double[] { rec[1], rec[0], rec[2], 1 }); // Add start event
9            list.Add(new double[] { rec[3], rec[0], rec[2], - 1 }); // Add end event
10        }
11        // Sort the list by y-axis
12        list.Sort((a, b) => (a[0] != b[0] ? a[0].CompareTo(b[0]) : a[3] * a[1] - b[3] * b[1]));
13        var active = new List<int[]>();
14        int n = rectangles.Length, cur = 0;
15        long res = 0, width = 0;
16        foreach (var l in list) {
17            int y = (int)l[0], left = (int)l[1], right = (int)l[2], sig = (int)l[3];
18            res = (long)((res + width * (y - cur)) % mod);
19            cur = y; // Update the current position to y
20            if (sig == 1) active.Add(new int[] { left, right }); // If it is start event, add to list
21            else active.RemoveAll(a => a[0] == left && a[1] == right); // If it is close event, remove from list
22            active.Sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // Sort the active list
23            width = 0; // Reset width to 0
24            int cur_left = -1, cur_right = -1; // Set current left and right to -1
25            foreach (var a in active) { // Traverse the active list to consolidate width
26                cur_left = Math.Max(cur_left, a[0]);
27                cur_right = Math.Max(cur_right, a[1]);
28                if (cur_left >= cur_right) {
29                    width += cur_right - a[0];
30                    cur_left = a[0];
31                    cur_right = a[1];
32                }
33            }
34        }
35        return (int)res;
36    }
37}

JavaScript Solution

1
2javascript
3const rectangleArea = function(rectangles) {
4    const MOD = 10**9 + 7;
5   
6    let events = [];
7    for (let [x1, y1, x2, y2] of rectangles) {
8        events.push([y1, x1, x2, 1]);
9        events.push([y2, x1, x2, -1]);
10    }
11   
12    // Sort the events
13    events.sort((a, b) => a[0] - b[0]);
14
15    let active = new Map();
16    let area = 0;
17    let cur_y = events[0][0];
18   
19    // Go through each event
20    for (let [y, x1, x2, sig] of events) {
21        // For the y-range between the current event and the last event, increase the answer by the sum of widths
22        let sum = 0, cur = -1;
23       
24        for (let [x, count] of active) {
25            if (cur >= 0 && count > 0) sum += x - cur;
26            cur = x;
27        }
28       
29        area += sum * (y - cur_y);
30        area %= MOD;
31       
32        cur_y = y;
33       
34        // Update active intervals
35        let count = active.get(x1) || 0;
36        if (count + sig > 0) active.set(x1, count + sig);
37        else active.delete(x1);
38       
39        count = active.get(x2) || 0;
40        if (count - sig > 0) active.set(x2, count - sig);
41        else active.delete(x2);
42    }
43   
44    return area;
45};

The different code snippets outlined above illustrate how to solve the problem using different programming languages, such as Python, Java, JavaScript, C++, and C#.

The takeaways from these solutions are:

1. The line sweep algorithm is applied across all the languages. This algorithm is a computational geometry algorithm for efficiently solving problems on the plane.

2. In all solutions, the coordinates of the corners of the rectangles are turned into events. These events are sorted based on their x-coordinates. This way, the algorithm can ensure that the events are processed in the correct order.

3. The vertices are processed one by one. If a vertex is on the left edge of a rectangle, the rectangle's vertical line segment is added to the line sweep state. If a vertex is on the right edge of a rectangle, its line segment is removed from the state.

4. The line sweep algorithm requires understanding and manipulation of data structures. In the Python solution, they use a sorted list of pairs to represent the active y-ranges. Java uses an ArrayList to maintain the active y-ranges, whereas C# and JavaScript use a Map to represent the same.

5. In the Java, C++, and C# solutions, a helper function is used to calculate the width covered by the active intervals.

6. In the JavaScript solution, they use a Map to represent active x-ranges. This allows for easier addition and removal of active x-ranges.

7. The final area is calculated by multiplying the sum of widths of the current active x-ranges with the difference in y-values between the current and the previous event. This area is accumulated and returned as the answer, with the modulo operation applied to prevent overflow.

Each of these solutions offers a different perspective on how to apply the line sweep algorithm to solve this problem. The key is understanding how the algorithm works and how to effectively use data structures to assist in the computation.