Rectangle Overlap LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple DocuSign Facebook Google Microsoft Oracle Qualcomm Samsung ServiceNow Uber
Geometry MathViews 3076

Problem Statement:

Rectangle Overlap LeetCode Solution – says that 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.

Examples:

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

Approach:

Idea:

The problem may seem difficult in the beginning if we go on to code for the conditions where the 2 rectangles overlap each other. A better idea will be to look for conditions when the 2 rectangles don’t overlap each other, i.e., the first rectangle lies either to the left, right, top, or bottom of the second rectangle. We just need to check for a single coordinate for each of the 4 cases. If the first rectangle lies to the left of the second rectangle then its x2 coordinate will always be less than equal to the x1 coordinate of the second rectangle. Similarly, we can deduce for the other 3 cases. Check out the well-commented code better understanding of the solution.

We can use basic maths to solve the problem efficiently.

Code:

C++ Solution:

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        // position of first rectangle w.r.t second rectangle.
        
        // left
        if(rec1[2]<=rec2[0])
            return false;
        
        // right
        if(rec1[0]>=rec2[2])
            return false;
        
        // top
        if(rec1[1]>=rec2[3])
            return false;   
        
        //bottom
        if(rec1[3]<=rec2[1])
            return false;
        
        return true;
    }
};

Python Solution:

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # position of first rectangle w.r.t second rectangle.
        
        # left
        if rec1[2]<=rec2[0]:
            return False
        
        # right
        if rec1[0]>=rec2[2]:
            return False
        
        # top
        if rec1[1]>=rec2[3]:
            return False
        
        # bottom
        if rec1[3]<=rec2[1]:
            return False
        
        return True

Complexity Analysis of Rectangle Overlap Leetcode Solution:

  • Time Complexity: The time complexity of the above code is  since all comparisons will be done in a constant amount of time and we aren’t using any linear array hence O(1).
  • Space Complexity: The space complexity of the above code is  as we did not use any extra space.
Translate »