Rectangle Area

Medium
1299.

Rectangle Area

Rectangle Area is a medium coding problem on math and geometry, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} ax1
 * @param {number} ay1
 * @param {number} ax2
 * @param {number} ay2
 * @param {number} bx1
 * @param {number} by1
 * @param {number} bx2
 * @param {number} by2
 * @return {number}
 */
var computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Add the two areas, then remove whatever was counted twice.

  2. Hint 2

    The shared part of two axis-parallel rectangles is itself a rectangle (or empty).

  3. 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

  1. Compute areaA = (ax2 - ax1) * (ay2 - ay1) and areaB the same way.
  2. The overlap's x-extent runs from max(ax1, bx1) to min(ax2, bx2); its width is the difference.
  3. Do the same in y to get the height.
  4. 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 - max is 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 - overlap

Java

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.

All 337 math problems · the whole catalogue