LogoKode$word

LeetCode 836: Rectangle Overlap – Java Solution, Explanation & Approach

Check whether two axis-aligned rectangles have a positive-area intersection using simple coordinate and boundary conditions.

Krishna Shrivastava
23 views
LinkedInGithubX
0
0
LeetCodeJavaRectangle OverlapGeometryArraysCoordinatesMathEasy
LeetCode 836: Rectangle Overlap – Java Solution, Explanation & Approach
Listen to articleAudio version
Ad

Introduction

LeetCode 836, Rectangle Overlap, is a simple geometry problem that tests an important idea: how to determine whether two ranges actually intersect.

Each rectangle is represented using four coordinates:

[x1, y1, x2, y2]

where:

  1. (x1, y1) → bottom-left corner
  2. (x2, y2) → top-right corner

The rectangles are axis-aligned, so their sides are always parallel to the X and Y axes.

The important part is that touching is not considered overlap.

For example, if two rectangles share only an edge or a corner, the answer must be false.

The solution can be built entirely using coordinate comparisons, without calculating the actual intersection area.

Some example testcase with visualized coordinates:-

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

Question Link

LeetCode 836 – Rectangle Overlap

Understanding the Idea

For two rectangles to have a positive-area overlap, they must overlap in both dimensions:

  1. Along the X-axis
  2. Along the Y-axis

If they fail to overlap in either dimension, the rectangles cannot overlap.

For example, if one rectangle is completely above another:

There is no overlap.

The same happens if one rectangle is completely to the left or right of the other.

Approach

The solution first extracts the four important boundaries of both rectangles:

Rectangle 1:
left = rec1[0]
bottom = rec1[1]
right = rec1[2]
top = rec1[3]

Rectangle 2:
left = rec2[0]
bottom = rec2[1]
right = rec2[2]
top = rec2[3]

Then the solution checks whether the rectangles are separated.

Check vertical separation

if(rect1h1 >= rect2h2 || rect2h1 >= rect1h2){
return false;
}

If the bottom of Rectangle 1 is at or above the top of Rectangle 2, they do not overlap.

Similarly, if the bottom of Rectangle 2 is at or above the top of Rectangle 1, there is no overlap.

The use of >= is important because rectangles that only touch an edge must return false.

Check horizontal separation

if(rect1l1 >= rect2l2 || rect2l1 >= rect1l2){
return false;
}

This checks whether one rectangle is completely to the left of the other.

Again, >= handles the edge-touching case.

After these separation checks pass, the rectangles must overlap with positive width and height.

Java Solution

class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {

boolean leno = false;
boolean heio = false;

int rect1l1 = rec1[0];
int rect1l2 = rec1[2];
int rect1h1 = rec1[1];
int rect1h2 = rec1[3];

int rect2l1 = rec2[0];
int rect2l2 = rec2[2];
int rect2h1 = rec2[1];
int rect2h2 = rec2[3];

// Check if the rectangles are separated vertically
if (rect1h1 >= rect2h2 || rect1l1 >= rect2l2) {
return false;
}

// Check if the rectangles are separated horizontally
if (rect2h1 >= rect1h2 || rect2l1 >= rect1l2) {
return false;
}

// There is horizontal overlap
if (rect1l2 > rect2l1) {
leno = true;
}

// There is vertical overlap
if (leno && rect1h2 <= rect2h2) {
heio = true;
}

if (leno && rect1h2 > rect2h2) {
heio = true;
}

return leno && heio;
}
}

Dry Run

Consider:

rec1 = [0,0,2,2]
rec2 = [1,1,3,3]

Rectangle 1:

left = 0
bottom = 0
right = 2
top = 2

Rectangle 2:

left = 1
bottom = 1
right = 3
top = 3

Vertical check

rect1 bottom >= rect2 top
0 >= 3 → false

and

rect2 bottom >= rect1 top
1 >= 2 → false

So they are not vertically separated.

Horizontal check

rect1 left >= rect2 right
0 >= 3 → false

and

rect2 left >= rect1 right
1 >= 2 → false

So they are not horizontally separated either.

Therefore, there is a positive-area intersection.

Answer = true

The overlapping region is:

x: 1 to 2
y: 1 to 2

which has positive width and height.

Why Edge Touching Returns False

Consider:

rec1 = [0,0,1,1]
rec2 = [1,0,2,1]

The rectangles touch at x = 1, but there is no positive-width intersection.

The condition:

rect2l1 >= rect1l2

becomes:

1 >= 1

which is true.

Therefore:

return false;

This is why >= is used instead of simply >.

A Useful Way to Think About the Problem

A rectangle overlap problem can be reduced to this simple rule:

If the rectangles are separated in X or separated in Y → no overlap. Otherwise → overlap.

The four separation cases are:

  1. Rectangle 1 is above Rectangle 2
  2. Rectangle 2 is above Rectangle 1
  3. Rectangle 1 is left of Rectangle 2
  4. Rectangle 2 is left of Rectangle 1

If none of these situations occurs, the rectangles overlap.

Complexity Analysis

There are only a constant number of coordinate comparisons.

Time Complexity: O(1)

Space Complexity: O(1)

No loops, additional arrays, or data structures are required.

Code Improvement

The current solution works, but the final leno and heio checks are more complicated than necessary.

Once all four separation cases have been eliminated, overlap is already guaranteed.

The same idea can therefore be written more directly:

class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {

// No vertical overlap
if (rec1[1] >= rec2[3] || rec2[1] >= rec1[3]) {
return false;
}

// No horizontal overlap
if (rec1[0] >= rec2[2] || rec2[0] >= rec1[2]) {
return false;
}

return true;
}
}

This version has exactly the same asymptotic complexity but makes the core geometry easier to recognize.

Interview Tip

For coordinate and geometry problems, avoid immediately trying to calculate the intersection area.

A better first question is:

"When can the two objects definitely NOT overlap?"

For rectangles, there are only four separation cases. Once those are handled, the remaining case automatically represents a positive-area overlap.

This "check the impossible cases first" technique is useful in many interval and geometry problems.

Conclusion

LeetCode 836 is a good example of how a seemingly geometric problem can be solved using simple comparisons.

The key observation is that two rectangles overlap only when they have overlap on both the X-axis and Y-axis. If one rectangle is completely separated from the other in either direction, the answer is false.

The important boundary detail is using >=, because merely touching at an edge or corner does not count as an overlap.

Related Articles

LeetCode 835: Image Overlap – Java Matrix Translation Solution

LeetCode 835: Image Overlap – Java Matrix Translation Solution

Find the maximum overlap between two binary images by translating one matrix in every possible direction.

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

Learn how to solve LeetCode 1855 using the two-pointer technique. Includes intuition, dry run, optimized Java code, and alternative approaches.

Read Article
Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
Ai Assistant Kas