Rectangle Overlap - Practice Coding Problems

Rectangle Overlap - Problem

Math Geometry Easy

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

Input & Output

Example 1 — Overlapping Rectangles

$ Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]

› Output: true

💡 Note: Rectangle 1 spans from (0,0) to (2,2) and Rectangle 2 spans from (1,1) to (3,3). They overlap in the region from (1,1) to (2,2), which has positive area.

Example 2 — Non-Overlapping Rectangles

$ Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]

› Output: false

💡 Note: Rectangle 1 is at (0,0)-(1,1) and Rectangle 2 is at (2,2)-(3,3). They are completely separate with no overlapping area.

Example 3 — Touching Edges

$ Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]

› Output: false

💡 Note: The rectangles share an edge but do not overlap. Touching at edges or corners doesn't count as overlapping since the intersection area is zero.

Constraints

rec1.length == 4
rec2.length == 4
-10⁹ ≤ rec1[i], rec2[i] ≤ 10⁹
rec1[0] ≤ rec1[2] and rec1[1] ≤ rec1[3] (valid rectangle)
rec2[0] ≤ rec2[2] and rec2[1] ≤ rec2[3] (valid rectangle)

Visualization

Tap to expand

Understanding the Visualization

Input

Two rectangles represented as [x1,y1,x2,y2] coordinates

Process

Check if rectangles have overlapping area

Output

Return true if overlap exists, false otherwise

Key Takeaway

🎯 Key Insight: It's easier to detect when rectangles DON'T overlap (separation) than when they do

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to check when rectangles do NOT overlap rather than when they do. Two rectangles don't overlap if one is completely to the left, right, above, or below the other. Best approach is the optimized non-overlap condition check. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Corner Check	O(1)	O(1)	Check if any corner of one rectangle is inside the other
Optimized - Non-Overlap Conditions	O(1)	O(1)	Check mathematical conditions when rectangles do NOT overlap

Brute Force - Corner Check — Algorithm Steps

Generate all 4 corners for each rectangle
Check if any corner of rec1 is inside rec2
Check if any corner of rec2 is inside rec1

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Corners

Create all 4 corners for each rectangle

Check Containment

Test if any corner lies inside the other rectangle

Result

Return true if any corner is contained

Code -

solution.c — C

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

bool solution(int* rec1, int* rec2) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    
    // Check if any corner of rec1 is inside rec2
    int corners1[4][2] = {{x1, y1}, {x1, y2}, {x2, y1}, {x2, y2}};
    for (int i = 0; i < 4; i++) {
        int x = corners1[i][0], y = corners1[i][1];
        if (x3 < x && x < x4 && y3 < y && y < y4) {
            return true;
        }
    }
    
    // Check if any corner of rec2 is inside rec1
    int corners2[4][2] = {{x3, y3}, {x3, y4}, {x4, y3}, {x4, y4}};
    for (int i = 0; i < 4; i++) {
        int x = corners2[i][0], y = corners2[i][1];
        if (x1 < x && x < x2 && y1 < y && y < y2) {
            return true;
        }
    }
    
    // Check if one rectangle completely contains the other
    if (x1 <= x3 && y1 <= y3 && x2 >= x4 && y2 >= y4) {
        return true;
    }
    if (x3 <= x1 && y3 <= y1 && x4 >= x2 && y4 >= y2) {
        return true;
    }
    
    return false;
}

int main() {
    char line[100];
    int rec1[4], rec2[4];
    
    fgets(line, sizeof(line), stdin);
    sscanf(line, "[%d,%d,%d,%d]", &rec1[0], &rec1[1], &rec1[2], &rec1[3]);
    
    fgets(line, sizeof(line), stdin);
    sscanf(line, "[%d,%d,%d,%d]", &rec2[0], &rec2[1], &rec2[2], &rec2[3]);
    
    bool result = solution(rec1, rec2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed number of corner checks regardless of input size

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to store coordinates

✓ Linear Space

25.0K Views

Medium Frequency

~10 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

Brute Force - Corner Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler