223. Rectangle Area
Problem Description
The problem is to calculate the total area covered by two rectilinear rectangles in a 2D plane. We are given the coordinates of the bottom-left and top-right corners for both rectangles. The coordinates for the first rectangle are (ax1, ay1)
for the bottom-left corner and (ax2, ay2)
for the top-right corner. Similarly, the second rectangle is defined by (bx1, by1)
for the bottom-left corner and (bx2, by2)
for the top-right corner. The rectangles have sides parallel to the x and y axes, which means they are aligned vertically and horizontally without any rotation.
The task is to find the sum of the areas of both rectangles minus any overlapping area.
Intuition
To solve this problem, we first calculate the areas of both rectangles independently. To find the area of a rectangle, we multiply the width (x2 - x1
) by the height (y2 - y1
). However, if the rectangles overlap, we need to avoid double-counting the shared area.
We determine the overlapping region by comparing the rectangles' edges. The width of the overlap is the smaller of the widths of the endings (min(ax2, bx2)
) minus the larger of the starts (max(ax1, bx1)
), and similarly for the height with respect to the y-coordinates.
The crucial insight is that if there is no overlap, either the width or the height (or both) of the overlapping area will be negative, since one rectangle's start will be greater than the other's end. Since we cannot have a negative area for rectangles, which would imply no overlap, we take the maximum of the computed width and height with 0.
The total area covered by the two rectangles is then the sum of the areas of both rectangles minus the area of the overlap, which is the product of the overlapping width and height (only subtracted if they are positive).
Learn more about Math patterns.
Solution Approach
The solution uses a straightforward approach leveraging arithmetic calculations without the need for additional data structures or complex algorithms. The process can be broken down into the following steps:
-
Calculate the area of both rectangles separately:
- For the first rectangle, the area
a
is computed as(ax2 - ax1) * (ay2 - ay1)
. - Similarly, for the second rectangle, the area
b
is computed as(bx2 - bx1) * (by2 - by1)
.
- For the first rectangle, the area
-
Determine the dimensions of the overlap (if any):
- Compute the overlap width as the difference between the minimum of the right sides (
min(ax2, bx2)
) and the maximum of the left sides (max(ax1, bx1)
). - Similarly, compute the overlap height as the difference between the minimum of the top sides (
min(ay2, by2)
) and the maximum of the bottom sides (max(ay1, by1)
). - If the rectangles don't overlap, either the calculated width or height (or both) will be negative, which implies that there is no overlap.
- Compute the overlap width as the difference between the minimum of the right sides (
-
Calculate the area of the overlapping region if it exists:
- The area of the overlap should only be considered if both width and height are positive.
- The overlap area is calculated by multiplying the positive values of the computed width and height:
max(height, 0) * max(width, 0)
. - Using
max
function ensures that a negative width or height (indicating no overlap) results in zero overlapping area.
-
Combine the results to get the total area covered by the rectangles:
- Add the area of both rectangles:
a + b
. - Subtract the overlap area only if it is positive, which is ensured by the previous step.
- Add the area of both rectangles:
The final result, which is the total area covered by the two rectangles, is thus calculated by a + b - max(height, 0) * max(width, 0)
.
No additional data structures or complex algorithms are necessary because the solution relies solely on conditional arithmetic. This approach is efficient as it calculates the required value with a constant number of arithmetic operations and in constant time complexity, i.e., O(1)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us illustrate the solution approach with a small example:
Assume we have two rectangles. The first rectangle A has coordinates of its bottom-left and top-right corners as (1, 2)
and (5, 5)
, respectively. The second rectangle B has corners at (3, 1)
and (7, 4)
.
Step 1: Calculate the area of both rectangles separately:
- Area of rectangle A (
a
):(5 - 1) * (5 - 2) = 4 * 3 = 12
- Area of rectangle B (
b
):(7 - 3) * (4 - 1) = 4 * 3 = 12
Step 2: Determine the dimensions of the overlap:
- Overlap width:
min(ax2, bx2) - max(ax1, bx1) = min(5, 7) - max(1, 3) = 5 - 3 = 2
- Overlap height:
min(ay2, by2) - max(ay1, by1) = min(5, 4) - max(2, 1) = 4 - 2 = 2
Step 3: Calculate the area of the overlapping region if it exists:
- Since both the overlap width and height are positive, we calculate the overlap area:
- Overlap area:
max(height, 0) * max(width, 0) = max(2, 0) * max(2, 0) = 2 * 2 = 4
Step 4: Combine the results to get the total area covered by the rectangles:
- Sum of both rectangles' areas:
a + b = 12 + 12 = 24
- Subtract the overlap area (positive) to avoid double counting:
24 - 4 = 20
The total area covered by the two rectangles is 20 square units. This example demonstrates the efficient use of conditional arithmetic to handle potential overlaps in the calculation of combined rectangular areas.
Solution Implementation
1class Solution:
2 def computeArea(self, A_x1: int, A_y1: int, A_x2: int, A_y2: int,
3 B_x1: int, B_y1: int, B_x2: int, B_y2: int) -> int:
4 # Area of the first rectangle (A)
5 area_A = (A_x2 - A_x1) * (A_y2 - A_y1)
6
7 # Area of the second rectangle (B)
8 area_B = (B_x2 - B_x1) * (B_y2 - B_y1)
9
10 # Computing the width of the overlapping area
11 # The overlap width is the smaller of the rightmost x minus the larger of the leftmost x
12 overlap_width = min(A_x2, B_x2) - max(A_x1, B_x1)
13
14 # Computing the height of the overlapping area
15 # The overlap height is the smaller of the topmost y minus the larger of the bottommost y
16 overlap_height = min(A_y2, B_y2) - max(A_y1, B_y1)
17
18 # Computing the area of overlapping if both width and height are positive (there is an overlap)
19 overlap_area = max(overlap_width, 0) * max(overlap_height, 0)
20
21 # Total combined area is the sum of both rectangle areas minus the overlapping area
22 return area_A + area_B - overlap_area
23
1class Solution {
2 public int computeArea(int A_x1, int A_y1, int A_x2, int A_y2,
3 int B_x1, int B_y1, int B_x2, int B_y2) {
4 // Calculate the area of the first rectangle
5 int areaA = (A_x2 - A_x1) * (A_y2 - A_y1);
6
7 // Calculate the area of the second rectangle
8 int areaB = (B_x2 - B_x1) * (B_y2 - B_y1);
9
10 // Calculate the width of the overlapping area
11 int overlapWidth = Math.min(A_x2, B_x2) - Math.max(A_x1, B_x1);
12
13 // Calculate the height of the overlapping area
14 int overlapHeight = Math.min(A_y2, B_y2) - Math.max(A_y1, B_y1);
15
16 // Ensure that the overlap width and height are non-negative
17 overlapWidth = Math.max(overlapWidth, 0);
18 overlapHeight = Math.max(overlapHeight, 0);
19
20 // Calculate the area of the overlapping region
21 int overlapArea = overlapWidth * overlapHeight;
22
23 // Combine the areas of both rectangles and subtract the overlapping area
24 return areaA + areaB - overlapArea;
25 }
26}
27
1class Solution {
2public:
3 int computeArea(int ax1, int ay1, int ax2, int ay2,
4 int bx1, int by1, int bx2, int by2) {
5 // Compute the area of the first rectangle: AreaA
6 int areaA = (ax2 - ax1) * (ay2 - ay1);
7
8 // Compute the area of the second rectangle: AreaB
9 int areaB = (bx2 - bx1) * (by2 - by1);
10
11 // Calculate the width of the overlapping area
12 int overlapWidth = std::min(ax2, bx2) - std::max(ax1, bx1);
13
14 // Calculate the height of the overlapping area
15 int overlapHeight = std::min(ay2, by2) - std::max(ay1, by1);
16
17 // Calculate the area of the overlapping region, guarding against no overlap scenario
18 // If no overlap, result is zero (overlapWidth or overlapHeight could be negative)
19 int overlapArea = std::max(overlapHeight, 0) * std::max(overlapWidth, 0);
20
21 // Return the sum of both areas minus the overlapping area
22 return areaA + areaB - overlapArea;
23 }
24};
25
1/**
2 * Computes the total area covered by two rectangles in a 2D plane.
3 * The rectangles are aligned with the x and y axes.
4 *
5 * @param {number} ax1 - The x-coordinate of the bottom-left corner of the first rectangle.
6 * @param {number} ay1 - The y-coordinate of the bottom-left corner of the first rectangle.
7 * @param {number} ax2 - The x-coordinate of the upper-right corner of the first rectangle.
8 * @param {number} ay2 - The y-coordinate of the upper-right corner of the first rectangle.
9 * @param {number} bx1 - The x-coordinate of the bottom-left corner of the second rectangle.
10 * @param {number} by1 - The y-coordinate of the bottom-left corner of the second rectangle.
11 * @param {number} bx2 - The x-coordinate of the upper-right corner of the second rectangle.
12 * @param {number} by2 - The y-coordinate of the upper-right corner of the second rectangle.
13 * @return {number} - The combined area of both rectangles.
14 */
15function computeArea(
16 ax1: number,
17 ay1: number,
18 ax2: number,
19 ay2: number,
20 bx1: number,
21 by1: number,
22 bx2: number,
23 by2: number,
24): number {
25 // Area of the first rectangle
26 const areaOfFirstRectangle = (ax2 - ax1) * (ay2 - ay1);
27 // Area of the second rectangle
28 const areaOfSecondRectangle = (bx2 - bx1) * (by2 - by1);
29
30 // Calculate the width of the overlapping area
31 const overlapWidth = Math.min(ax2, bx2) - Math.max(ax1, bx1);
32 // Calculate the height of the overlapping area
33 const overlapHeight = Math.min(ay2, by2) - Math.max(ay1, by1);
34
35 // Calculate the area of the overlapping region; if there is no overlap,
36 // this would be zero as Math.max would handle negative values.
37 const overlapArea = Math.max(overlapWidth, 0) * Math.max(overlapHeight, 0);
38
39 // The total area is the sum of the areas of both rectangles minus the overlap area
40 return areaOfFirstRectangle + areaOfSecondRectangle - overlapArea;
41}
42
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(1)
. This is because all operations performed to calculate the areas of rectangles and the overlapping region take a constant amount of time. Each operation involves basic arithmetic calculations that do not depend on the size of the input.
Space Complexity
The space complexity of the code is also O(1)
. The amount of memory used does not increase with the size of the input, as there are only a fixed number of integer variables assigned (a
, b
, width
, and height
) and no use of any data structures that could scale with input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.