Skip to main content

Rectangle Area

LeetCode 223 | Difficulty: Medium​

Medium

Problem Description​

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:

- `-10^4 <= ax1 <= ax2 <= 10^4`

- `-10^4 <= ay1 <= ay2 <= 10^4`

- `-10^4 <= bx1 <= bx2 <= 10^4`

- `-10^4 <= by1 <= by2 <= 10^4`

Topics: Math, Geometry

Approach​

Mathematical​

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Solutions​

Solution 1: C# (Best: 28 ms)​

MetricValue
Runtime28 ms
Memory28.3 MB
Date2022-01-27
Solution
public class Solution {
    public int ComputeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int area1 = (ax2-ax1) * (ay2-ay1);
    int area2 = (bx2-bx1) * (by2-by1);
    
    int left = Math.Max(ax1, bx1);
    int right = Math.Min(ax2, bx2);
    int bottom = Math.Max(ay1, by1);
    int top = Math.Min(ay2, by2);
    int overlap = 0;
    if(right>left && top> bottom)
    {
        overlap = (right-left) * (top -bottom);
    }
    return area1+area2-overlap;
    }
}

Complexity Analysis​

ApproachTimeSpace
Solution$O(n)$$O(1) to O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.