836. Rectangle Overlap Solution

The problem

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.

Example 1:

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

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

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

Constraints:

rec1.length == 4
rec2.length == 4
-10⁹ <= rec1[i], rec2[i] <= 10⁹
rec1 and rec2 represent a valid rectangle with a non-zero area.

Approach overview

Problem Overview: You receive the coordinates of two axis-aligned rectangles defined by their bottom-left and top-right corners. The task is to determine whether these rectangles overlap with a positive area. Touching edges or corners does not count as overlap.

Approach 1: Rectangle Non-Overlap Conditions (O(1) time, O(1) space)

The simplest way to detect overlap is to check if the rectangles are separated. Two rectangles do not overlap when one lies completely to the left, right, above, or below the other. These four cases can be expressed with coordinate comparisons: rect1.right <= rect2.left, rect1.left >= rect2.right, rect1.top <= rect2.bottom, or rect1.bottom >= rect2.top. If any condition is true, there is no overlap. Otherwise the rectangles must intersect. This method relies on simple arithmetic comparisons, runs in constant time, and is typically the cleanest implementation for problems involving geometry and coordinate ranges.

Approach 2: Checking Overlap Using Intersection (O(1) time, O(1) space)

Another way to think about the problem is to compute the potential intersection region. The width of the intersection equals min(r1.right, r2.right) - max(r1.left, r2.left), and the height equals min(r1.top, r2.top) - max(r1.bottom, r2.bottom). If both width and height are strictly greater than zero, the rectangles overlap with positive area. This approach directly models the intersection rectangle and is often easier to visualize when solving coordinate problems involving math or bounding boxes. It’s also a common pattern when extending to multiple rectangles or computing intersection area.

Recommended for interviews: The non-overlap condition approach is what interviewers usually expect. It shows you understand the geometric constraints and can convert them into concise logical checks. The intersection approach demonstrates strong spatial reasoning and becomes useful when follow-ups ask for intersection area or rectangle merging.

Approach 1: Rectangle Non-Overlap Conditions

This approach checks if there are conditions that confirm non-overlapping rectangles. Specifically, two rectangles do not overlap if:

The right side of the first rectangle is to the left of the left side of the second rectangle.
The left side of the first rectangle is to the right of the right side of the second rectangle.
The top side of the first rectangle is below the bottom side of the second rectangle.
The bottom side of the first rectangle is above the top side of the second rectangle.

If any of these conditions are true, the rectangles do not overlap. Otherwise, they do overlap.

Python

def isRectangleOverlap(rec1, rec2):
    return not (rec1[2] <= rec2[0] or  
                rec1[0] >= rec2[2] or  
                rec1[3] <= rec2[1] or  
                rec1[1] >= rec2[3])

Java

public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    return rec1[2] > rec2[0] &&
           rec1[0] < rec2[2] &&
           rec1[3] > rec2[1] &&
           rec1[1] < rec2[3];
}

C++

bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
    return !(rec1[2] <= rec2[0] || 
             rec1[0] >= rec2[2] || 
             rec1[3] <= rec2[1] || 
             rec1[1] >= rec2[3]);
}

JavaScript

function isRectangleOverlap(rec1, rec2) {
    return !(rec1[2] <= rec2[0] ||
             rec1[0] >= rec2[2] ||
             rec1[3] <= rec2[1] ||
             rec1[1] >= rec2[3]);
}

#include <stdbool.h>
bool isRectangleOverlap(int* rec1, int* rec2) {
    return !(rec1[2] <= rec2[0] ||
             rec1[0] >= rec2[2] ||
             rec1[3] <= rec2[1] ||
             rec1[1] >= rec2[3]);
}

public bool IsRectangleOverlap(int[] rec1, int[] rec2) {
    return !(rec1[2] <= rec2[0] ||
             rec1[0] >= rec2[2] ||
             rec1[3] <= rec2[1] ||
             rec1[1] >= rec2[3]);
}

The function checks whether any of the non-overlapping conditions are true. If none are true, it means the rectangles overlap.

Complexity

Time Complexity: O(1), since the operation involves a constant number of comparisons.
Space Complexity: O(1), since the space used by the function is constant with respect to inputs.

Try this approach in the editor

Approach 2: Checking Overlap Using Intersection

This approach computes the potential intersecting rectangle and verifies if its calculated dimensions form a valid rectangle with a positive area. The logic involves:

Calculating the intersection rectangle as:
- Left side: max(rec1[0], rec2[0])
- Right side: min(rec1[2], rec2[2])
- Bottom side: max(rec1[1], rec2[1])
- Top side: min(rec1[3], rec2[3])
Checking if the intersection's width and height are both positive.

Python

def isRectangleOverlap(rec1, rec2):
    x_overlap = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0])
    y_overlap = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])
    return x_overlap and y_overlap

Java

public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    boolean xOverlap = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);
    boolean yOverlap = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
    return xOverlap && yOverlap;
}

C++

bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
    bool x_overlap = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]);
    bool y_overlap = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]);
    return x_overlap && y_overlap;
}

JavaScript

function isRectangleOverlap(rec1, rec2) {
    const xOverlap = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);
    const yOverlap = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
    return xOverlap && yOverlap;
}

#include <stdbool.h>
bool isRectangleOverlap(int* rec1, int* rec2) {
    int xOverlap = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]);
    int yOverlap = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]);
    return xOverlap && yOverlap;
}

public bool IsRectangleOverlap(int[] rec1, int[] rec2) {
    bool xOverlap = Math.Min(rec1[2], rec2[2]) > Math.Max(rec1[0], rec2[0]);
    bool yOverlap = Math.Min(rec1[3], rec2[3]) > Math.Max(rec1[1], rec2[1]);
    return xOverlap && yOverlap;
}

The function calculates potential overlapping parts along both axes and ensures these parts form an area (both x and y overlap must be true).

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Determine Non-Overlap Cases

Let the coordinates of rectangle rec1 be (x_1, y_1, x_2, y_2), and the coordinates of rectangle rec2 be (x_3, y_3, x_4, y_4).

The rectangles rec1 and rec2 do not overlap if any of the following conditions are met:

y_3 geq y_2: rec2 is above rec1;
y_4 leq y_1: rec2 is below rec1;
x_3 geq x_2: rec2 is to the right of rec1;
x_4 leq x_1: rec2 is to the left of rec1.

If none of the above conditions are met, the rectangles rec1 and rec2 overlap.

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function isRectangleOverlap(rec1: number[], rec2: number[]): boolean {
    const [x1, y1, x2, y2] = rec1;
    const [x3, y3, x4, y4] = rec2;
    return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1);
}

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
	x1, y1, x2, y2 := rec1[0], rec1[1], rec1[2], rec1[3]
	x3, y3, x4, y4 := rec2[0], rec2[1], rec2[2], rec2[3]
	return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Rectangle Non-Overlap Conditions	Time Complexity: O(1), since the operation involves a constant number of comparisons. Space Complexity: O(1), since the space used by the function is constant with respect to inputs.
Checking Overlap Using Intersection	Time Complexity: O(1) Space Complexity: O(1)
Determine Non-Overlap Cases	–

Complexity analysis

Approach	Time	Space	When to Use
Rectangle Non-Overlap Conditions	O(1)	O(1)	Best general solution. Minimal logic using four separation checks.
Checking Overlap Using Intersection	O(1)	O(1)	Useful when computing intersection dimensions or area.

Frequently asked questions

Is Rectangle Overlap easy or hard?

Rectangle Overlap is classified as an Easy problem. The challenge mainly involves recognizing the four non-overlap cases and handling edge cases where rectangles only touch but do not share area.

How to solve Rectangle Overlap in O(1)?

Use rectangle separation logic. Check whether one rectangle lies entirely to the left, right, above, or below the other using coordinate comparisons. If none of these conditions hold, the rectangles must overlap with positive area.

Rectangle Overlap Python or Java solution?

The solution is identical across languages such as Python, Java, C++, and JavaScript. Implement the non-overlap condition checks using simple if statements and return the negation of those conditions to determine overlap.

What is the best approach for Rectangle Overlap?

The best approach checks the four non-overlap conditions between the rectangles. If one rectangle is completely left, right, above, or below the other, they do not overlap. Otherwise an overlap exists. This solution runs in O(1) time and O(1) space and requires only a few coordinate comparisons.

What data structure is used in Rectangle Overlap?

No special data structure is required. The problem relies on basic arithmetic comparisons between rectangle coordinates. It mainly falls under geometry and math-based problem solving.

What is the time complexity of Rectangle Overlap?

Rectangle Overlap can be solved in O(1) time because the algorithm performs a constant number of coordinate comparisons. No loops or additional data structures are required. Space complexity is also O(1).

Is Rectangle Overlap asked at Google, Amazon, or Meta?

Rectangle geometry problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. They test your ability to reason about coordinate systems, edge conditions, and simple geometric constraints.

Rectangle Overlap solution and explanation

The problem

Approach overview

Approach 1: Rectangle Non-Overlap Conditions

Approach 2: Checking Overlap Using Intersection

Approach 3: Determine Non-Overlap Cases

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rectangle Overlap solution and explanation

The problem

Approach overview

Approach 1: Rectangle Non-Overlap Conditions

Approach 2: Checking Overlap Using Intersection

Approach 3: Determine Non-Overlap Cases

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems