LeetCode 850: Rectangle Area II Solution
Master LeetCode problem 850 (Rectangle Area II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
850. Rectangle Area II
Problem Explanation
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.
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 850 (Rectangle Area II)?
This page provides optimized solutions for LeetCode problem 850 (Rectangle Area II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 850 (Rectangle Area II)?
The time complexity for LeetCode 850 (Rectangle Area II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 850 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 850 in Java, C++, or Python.