How do you solve Rectangle Overlap on LeetCode?

Rectangle Overlap (LeetCode #836) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: Rectangles overlap if they do not satisfy any of the non-overlapping conditions.

What is the brute force solution for Rectangle Overlap?

The brute force approach for Rectangle Overlap is Brute Force, with O(1) time complexity and O(1) space complexity. To determine if two rectangles overlap, we can check if one rectangle is completely to the left, right, above, or below the other. If none of these conditions are true, they must overlap. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Rectangle Overlap?

Rectangle Overlap uses the following concepts: Math, Geometry. The recommended patterns to study are: Geometry, Coordinate Systems.

What are the interview tips for Rectangle Overlap?

Clearly explain your thought process as you derive the conditions for overlap. Consider edge cases, such as rectangles that only touch at the corners or edges. Practice writing concise code that directly implements your logic.

What are common mistakes when solving Rectangle Overlap?

Students often forget to check all four conditions for non-overlapping rectangles. Confusing the coordinates of the rectangles can lead to incorrect comparisons.

#836

Rectangle Overlap

Easy

MathGeometryGeometryCoordinate Systems

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(1)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

The optimal solution uses the same logic as the brute force but is more concise. We can combine the checks into a single return statement for clarity and efficiency.

⚙️

Algorithm

1 steps

1Step 1: Return true if the rectangles overlap, which is determined by checking if none of the conditions for non-overlapping rectangles are satisfied.

solution.py2 lines

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

ℹ

Complexity note: The time complexity remains O(1) as we are still performing a fixed number of checks. The space complexity is O(1) since we are not using any additional data structures.

1Rectangles overlap if they do not satisfy any of the non-overlapping conditions.
2The conditions for non-overlapping rectangles are based on their edges.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.