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.
1#include <stdio.h>
2
3int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int
This program first computes the rectangles' areas using their width and height. It then calculates the overlap width and height based on intersecting limits of x and y coordinates. If these intersections are valid (width and height are positive), it then computes the overlap area and subtracts it from the total area of both rectangles. Finally, it outputs the total area covered by the rectangles.
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.
In Python, a helper function detects overlap by checking coordinate limits. Overlap adjustments are made when rectangles overlap, resulting in the total area covered after subtracting the duplicated overlap.