Rectangle Area II - Practice Coding Problems

Rectangle Area II - Problem

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [x₁, y₁, x₂, y₂] denotes the i-th rectangle where (x₁, y₁) are the coordinates of the bottom-left corner, and (x₂, y₂) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Two Overlapping Rectangles

$ Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]

› Output: 6

💡 Note: Three rectangles with some overlap. Rectangle 1: area 4, Rectangle 2: area 6, Rectangle 3: area 2. Total covered area after removing overlaps is 6.

Example 2 — Single Rectangle

$ Input: rectangles = [[0,0,1000000000,1000000000]]

› Output: 49

💡 Note: Single large rectangle. Area = 10^18, which modulo 10^9+7 equals 49.

Example 3 — No Overlap

$ Input: rectangles = [[0,0,1,1],[2,2,3,3]]

› Output: 2

💡 Note: Two rectangles with no overlap. Each has area 1, so total is 2.

Constraints

1 ≤ rectangles.length ≤ 200
rectangles[i].length == 4
0 ≤ x_i1, y_i1, x_i2, y_i2 ≤ 10⁹
x_i1 < x_i2 and y_i1 < y_i2

Visualization

Tap to expand

Understanding the Visualization

Input Rectangles

Multiple axis-aligned rectangles with possible overlaps

Find Union

Calculate total area covered by all rectangles

Output Area

Return total area modulo 10^9+7

Key Takeaway

🎯 Key Insight: Use coordinate compression and line sweep to efficiently calculate union area without double-counting overlaps

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is to use coordinate compression and line sweep algorithm. Instead of checking every point, we only consider boundaries of rectangles. The line sweep approach processes vertical strips and merges overlapping y-intervals. Time: O(n² log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Grid Coverage Check	O(n³)	O(n²)	Check coverage for every possible coordinate point in a compressed grid
Line Sweep Algorithm	O(n² log n)	O(n)	Sweep vertical line from left to right, tracking active rectangles and computing areas

Grid Coverage Check — Algorithm Steps

Step 1: Extract all unique x and y coordinates from rectangles
Step 2: Create a compressed grid using these coordinates
Step 3: For each grid cell, check if any rectangle covers it
Step 4: Sum areas of all covered cells

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Coordinates

Get all unique x,y coordinates from rectangles

Create Grid

Form compressed grid using these coordinates

Check Coverage

For each cell, check if any rectangle covers it

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_COORDS 2000

int compareInts(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int rectangles[][4], int rectCount) {
    if (rectCount == 0) return 0;
    
    int xCoords[MAX_COORDS], yCoords[MAX_COORDS];
    int xCount = 0, yCount = 0;
    
    // Extract unique coordinates
    for (int i = 0; i < rectCount; i++) {
        // Add x coordinates
        int found = 0;
        for (int j = 0; j < xCount; j++) {
            if (xCoords[j] == rectangles[i][0]) {
                found = 1;
                break;
            }
        }
        if (!found) xCoords[xCount++] = rectangles[i][0];
        
        found = 0;
        for (int j = 0; j < xCount; j++) {
            if (xCoords[j] == rectangles[i][2]) {
                found = 1;
                break;
            }
        }
        if (!found) xCoords[xCount++] = rectangles[i][2];
        
        // Add y coordinates
        found = 0;
        for (int j = 0; j < yCount; j++) {
            if (yCoords[j] == rectangles[i][1]) {
                found = 1;
                break;
            }
        }
        if (!found) yCoords[yCount++] = rectangles[i][1];
        
        found = 0;
        for (int j = 0; j < yCount; j++) {
            if (yCoords[j] == rectangles[i][3]) {
                found = 1;
                break;
            }
        }
        if (!found) yCoords[yCount++] = rectangles[i][3];
    }
    
    qsort(xCoords, xCount, sizeof(int), compareInts);
    qsort(yCoords, yCount, sizeof(int), compareInts);
    
    long long totalArea = 0;
    
    for (int i = 0; i < xCount - 1; i++) {
        for (int j = 0; j < yCount - 1; j++) {
            int x1 = xCoords[i], x2 = xCoords[i + 1];
            int y1 = yCoords[j], y2 = yCoords[j + 1];
            
            int covered = 0;
            for (int k = 0; k < rectCount; k++) {
                if (rectangles[k][0] <= x1 && x2 <= rectangles[k][2] && 
                    rectangles[k][1] <= y1 && y2 <= rectangles[k][3]) {
                    covered = 1;
                    break;
                }
            }
            
            if (covered) {
                totalArea = (totalArea + (long long)(x2 - x1) * (y2 - y1)) % MOD;
            }
        }
    }
    
    return totalArea;
}

int main() {
    int rectangles[1000][4];
    int rectCount = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1,x2,y2],...]
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            sscanf(ptr, "%d,%d,%d,%d", &rectangles[rectCount][0], &rectangles[rectCount][1], 
                   &rectangles[rectCount][2], &rectangles[rectCount][3]);
            rectCount++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(rectangles, rectCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for grid cells (O(n²)) and inner loop checking all rectangles (O(n))

⚠ Quadratic Growth

Space Complexity

O(n²)

Storing compressed coordinates arrays and grid coverage checks

⚠ Quadratic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Grid Coverage Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler