Skip to main content
Talentd

Rectangle Overlap - Solution & Explanation

EasyMathGeometry13 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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
  • -109 <= rec1[i], rec2[i] <= 109
  • 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.

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

Code

PythonC++JavaJavaScriptC#C

Python

C++

Java

JavaScript

C#

C

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.

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

Code

PythonC++JavaJavaScriptC#C

Python

C++

Java

JavaScript

C#

C

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Rectangle Non-Overlap ConditionsO(1)O(1)Best general solution. Minimal logic using four separation checks.
Checking Overlap Using IntersectionO(1)O(1)Useful when computing intersection dimensions or area.

Video Solution

LeetCode 836. Rectangle Overlap Solution Explained - Java • Nick White • 21,117 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Rectangle Overlap with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rectangle Area