Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.
The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).
The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).
Example 1:
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 Output: 45
Example 2:
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2 Output: 16
Constraints:
-104 <= ax1 <= ax2 <= 104-104 <= ay1 <= ay2 <= 104-104 <= bx1 <= bx2 <= 104-104 <= by1 <= by2 <= 104In #223 Rectangle Area, you are given the coordinates of two axis-aligned rectangles and must determine the total area they cover. A straightforward idea is to first compute the area of each rectangle independently using their corner coordinates. However, if the rectangles overlap, simply adding both areas would count the overlapping region twice.
The key insight is to detect whether an intersection region exists. By comparing the horizontal and vertical boundaries of both rectangles, you can determine the width and height of the potential overlap using min and max boundary checks. If both overlap dimensions are positive, the overlapping region must be subtracted from the sum of the two individual areas.
This approach relies purely on coordinate comparisons and arithmetic, making it efficient and easy to implement. Because the number of operations is constant regardless of input values, the algorithm runs in O(1) time with O(1) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Compute individual areas and subtract overlap | O(1) | O(1) |
NeetCode
This approach involves calculating the area of each rectangle separately, then finding the overlapping area, and subtracting it from the total. First, calculate the area of each rectangle by using the formula width multiplied by height. To find the overlap, determine the maximum of the bottom-left x and y coordinates, and the minimum of the top-right x and y coordinates. If the rectangles do intersect, subtract the overlap area from the sum of the rectangle areas to get the total covered area.
The time complexity is O(1) since it involves basic arithmetic operations, and the space complexity is also O(1) as no additional space is needed beyond a few variables.
1public class Solution {
2 public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, In this Java implementation, the rectangle areas are calculated first. The overlap is computed using Math.min and Math.max. The overlap area is considered in the result if it is positive by checking the conditions for overlapWidth and overlapHeight.
By using the coordinate sweep method, we can iterate through all points in a uniform grid covering both rectangles. This technique conceptualizes sweeping lines across the plane, adding and subtracting areas as intersections are counted. Use sorting and a plane-sweep technique to determine overlapping intervals more effectively.
The time complexity remains O(1) since it involves constant time computation, while the space complexity is also O(1) because it uses a constant number of variables.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry and coordinate-based problems like Rectangle Area sometimes appear in technical interviews. Companies may use them to test logical reasoning, boundary handling, and understanding of edge cases such as overlapping or non-overlapping shapes.
The optimal approach computes the area of both rectangles separately and then subtracts any overlapping region. The overlap can be detected by comparing the rectangle boundaries using min and max operations. This method runs in constant time because only a fixed number of arithmetic operations are required.
No special data structures are required for this problem. The solution relies on simple arithmetic and coordinate comparisons using variables. Since all calculations are constant-time, the space complexity remains O(1).
Overlap occurs when the horizontal ranges and vertical ranges of the rectangles intersect. By comparing the left, right, top, and bottom boundaries, you can determine whether an intersection region exists. If both overlap width and height are positive, an overlapping rectangle must be accounted for.
This JavaScript program checks for rectangle overlap and calculates total area accordingly. If conditions show overlap, it accounts for the overlapping area, minimizing redundant calculations.