836.Rectangle_Overlap(Easy).md

836. Rectangle Overlap (Easy)

Date and Time: Apr 1, 2025

Link: https://leetcode.com/problems/rectangle-overlap

Edge Case 1:

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

Walk-through:

We check check if rec1 is on the left/right/top/bottom of rec2. If rec1 is on the left/right of rec2, we know they will not overlap on the x axis, and there is no way to overlap on y axis as well. Same as checking the top/bottom, so the y axis will not overlap, and it doesn't matter for x axis.

If rec1 is not left/right/top/bottom of rec2, they must overlap.

Python Solution:

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # Pick rec2 as center, check if rec1 is around rec2 by its left, right, top, bottom. If none of them is true, they must overlap
        # x: rec1[2] <= rec2[0] (rec1 is on the left of rec2)
        # x: rec1[0] >= rec2[2] (rec1 is on the right of rec2)
        # y: rec1[1] >= rec2[3] (rec1 is on the top of rec2)
        # y: rec1[3] <= rec2[1] (rec1 is on the bottom of rec2)

        # TC: O(1), SC: O(1)
        return not (rec1[2] <= rec2[0] or 
                    rec1[0] >= rec2[2] or
                    rec1[1] >= rec2[3] or
                    rec1[3] <= rec2[1])

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