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 <= 104Problem Overview: You are given coordinates of two axis-aligned rectangles. Each rectangle is defined by its bottom-left and top-right corners. The task is to compute the total area covered by both rectangles combined, counting the overlapping region only once.
Approach 1: Calculate Areas Separately and Subtract Overlap (O(1) time, O(1) space)
This approach relies on straightforward math and geometry. First compute the area of each rectangle independently using (x2 - x1) * (y2 - y1). If the rectangles overlap, the overlapping region is counted twice, so you subtract it once from the sum of both areas.
To find the overlap, compute the intersection boundaries. The left boundary is max(ax1, bx1), the right boundary is min(ax2, bx2), the bottom boundary is max(ay1, by1), and the top boundary is min(ay2, by2). If right > left and top > bottom, the rectangles intersect and the overlap area is (right - left) * (top - bottom). Otherwise the overlap area is zero. This constant-time formula makes the solution extremely efficient and is the standard approach expected in interviews.
Approach 2: Coordinate Sweep Method (O(1) time, O(1) space)
The coordinate sweep (or sweep-line) idea comes from computational geometry. Imagine sweeping a vertical line across the plane and tracking active x-intervals of rectangles. For general rectangle union problems with many rectangles, you would create events for rectangle edges, sort them, and maintain active intervals to compute covered area.
For this specific problem with only two rectangles, the sweep concept simplifies significantly. You can treat the x-coordinates as interval segments and compute vertical coverage between boundaries. The result still reduces to detecting overlap between the rectangles and subtracting it from the combined area. This approach is conceptually useful because it scales to problems like rectangle union area or skyline computations, even though it does not provide performance benefits here.
Recommended for interviews: The direct area calculation with overlap subtraction is what interviewers expect. It shows you understand rectangle intersection logic and can derive the overlap boundaries quickly. The sweep-line method demonstrates deeper knowledge of computational geometry, but it is unnecessary for two rectangles. Start with the basic formula approach to show clear reasoning and optimal O(1) performance.
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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
This C variant checks if two rectangles can overlap by verifying bounding constraints. The rectangles' areas are computed, and the overlapping area is considered zero if there is no overlap. Otherwise, overlapping dimensions are calculated, and their areas are subtracted accordingly.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Calculate Areas Separately and Subtract Overlap | 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. |
| Coordinate Sweep Method | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Areas Separately and Subtract Overlap | O(1) | O(1) | Best for two rectangles. Simple math formula and optimal constant time. |
| Coordinate Sweep Method | O(1) | O(1) | Useful concept when extending the problem to many rectangles or computing union areas. |
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python • NeetCode • 287,824 views views
Watch 9 more video solutions →Practice Rectangle Area with our built-in code editor and test cases.
Practice on FleetCode