LeetCode 850: Rectangle Area II
Problem Description
Explanation
To solve this problem, we can break it down into two main steps:
- Calculate the total area covered by all rectangles without considering overlaps.
- Handle the overlapping areas by keeping track of the overlapped regions.
We can achieve this by iterating over each rectangle, updating the total area, and maintaining a set of coordinates to represent the overlapped regions. Finally, we can calculate the total area by subtracting the overlapped regions from the total area covered by all rectangles.
Time Complexity:
The time complexity of this approach is O(n^2) where n is the number of rectangles. This is because for each rectangle, we potentially need to check for overlap with each other rectangle.
Space Complexity:
The space complexity is O(n) to store the coordinates of the overlapped regions.
Solutions
class Solution {
public int rectangleArea(int[][] rectangles) {
Set<Long> set = new HashSet<>();
for (int[] rect : rectangles) {
updateSet(set, rect, 1);
}
long totalArea = calculateTotalArea(set);
return (int) (totalArea % 1_000_000_007);
}
private void updateSet(Set<Long> set, int[] rect, int sign) {
long key = getKey(rect[0], rect[1]);
set.add(key);
key = getKey(rect[0], rect[3]);
set.add(key);
key = getKey(rect[2], rect[1]);
set.add(key);
key = getKey(rect[2], rect[3]);
set.add(key);
}
private long getKey(int x, int y) {
return ((long) x << 32) + y;
}
private long calculateTotalArea(Set<Long> set) {
long totalArea = 0;
for (long coords : set) {
int x1 = (int) (coords >> 32);
int y1 = (int) coords;
long nextCoords = getNextCoord(set, x1);
if (nextCoords == -1) {
continue;
}
int x2 = (int) (nextCoords >> 32);
int y2 = (int) nextCoords;
totalArea += (long) (x2 - x1) * (y2 - y1);
}
return totalArea;
}
private long getNextCoord(Set<Long> set, int x) {
long res = -1;
for (long coords : set) {
int currX = (int) (coords >> 32);
if (currX > x) {
res = coords;
break;
}
}
return res;
}
}Related LeetCode Problems
Loading editor...