Rectangle Area — Solution in Python, Java & C++
Rectangle Area solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and geometry.
Rectangle Area is a medium coding problem on math and geometry, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Math, Geometry
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two rectangles lie in the plane with their sides parallel to the axes. Rectangle A has bottom-left corner (ax1, ay1) and top-right corner (ax2, ay2); rectangle B has bottom-left corner (bx1, by1) and top-right corner (bx2, by2).
Return the total area covered by the two rectangles together. Ground covered by both counts once.
A rectangle may be degenerate (zero width or zero height); it then covers no area.
Example 1
Input: ax1 = 0, ay1 = 0, ax2 = 4, ay2 = 3, bx1 = 2, by1 = 1, bx2 = 6, by2 = 5
Output: 24
Explanation: A covers 12, B covers 16, and they share the 2 x 2 square from (2,1) to (4,3), so 12 + 16 - 4 = 24.
Example 2
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16
Explanation: The rectangles coincide.
Example 3
Input: ax1 = 0, ay1 = 0, ax2 = 1, ay2 = 1, bx1 = 5, by1 = 5, bx2 = 7, by2 = 8
Output: 7
Constraints
-10^4 <= ax1 <= ax2 <= 10^4-10^4 <= ay1 <= ay2 <= 10^4-10^4 <= bx1 <= bx2 <= 10^4-10^4 <= by1 <= by2 <= 10^4
Hints for Rectangle Area
Hint 1
Add the two areas, then remove whatever was counted twice.
Hint 2
The shared part of two axis-parallel rectangles is itself a rectangle (or empty).
Hint 3
Its width is
min(ax2, bx2) - max(ax1, bx1)and its height is the same in y; it is empty if either is not positive.
How to solve Rectangle Area
Inclusion-exclusion: covered area = area(A) + area(B) - area(A ∩ B), and the intersection of two axis-parallel rectangles is found one axis at a time.
Approach
- Compute
areaA = (ax2 - ax1) * (ay2 - ay1)andareaBthe same way. - The overlap's x-extent runs from
max(ax1, bx1)tomin(ax2, bx2); its width is the difference. - Do the same in y to get the height.
- If both width and height are positive, subtract
width * height; otherwise subtract nothing.
Why it works
A point lies in both rectangles exactly when its x lies in both x-intervals and its y lies in both y-intervals, so the intersection is the product of the two interval intersections. An interval intersection [max of starts, min of ends] is empty when the start passes the end, which is why a non-positive width or height means no overlap. Adding both areas counts the intersection twice, so subtracting it once leaves every covered point counted exactly once.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- If the rectangles are apart,
min - maxis negative in that axis; multiplying two negative extents gives a positive bogus overlap, so test each sign before multiplying. - Rectangles that only touch along an edge share zero area.
- Each area is at most 4·10^8, so the sum still fits in 32 bits — but compute the overlap separately rather than as one big expression with signs mixed.
Reference solution
Python
def computeArea(ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
area_a = (ax2 - ax1) * (ay2 - ay1)
area_b = (bx2 - bx1) * (by2 - by1)
w = min(ax2, bx2) - max(ax1, bx1)
h = min(ay2, by2) - max(ay1, by1)
overlap = w * h if w > 0 and h > 0 else 0
return area_a + area_b - overlapJava
public static int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int w = Math.min(ax2, bx2) - Math.max(ax1, bx1);
int h = Math.min(ay2, by2) - Math.max(ay1, by1);
int overlap = (w > 0 && h > 0) ? w * h : 0;
return areaA + areaB - overlap;
}C++
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int w = min(ax2, bx2) - max(ax1, bx1);
int h = min(ay2, by2) - max(ay1, by1);
int overlap = (w > 0 && h > 0) ? w * h : 0;
return areaA + areaB - overlap;
}JavaScript
var computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
var areaA = (ax2 - ax1) * (ay2 - ay1);
var areaB = (bx2 - bx1) * (by2 - by1);
var w = Math.min(ax2, bx2) - Math.max(ax1, bx1);
var h = Math.min(ay2, by2) - Math.max(ay1, by1);
var overlap = (w > 0 && h > 0) ? w * h : 0;
return areaA + areaB - overlap;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.