algoadvance

Leetcode 836. Rectangle Overlap

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. Two rectangles overlap if the area of their intersection is positive.

To be clear, two rectangles that only touch at the corner or edge do not overlap.

Given two (axis-aligned) rectangles, return true if they overlap, otherwise return false.

Clarifying Questions:

  1. Input Constraints:
    • Are the coordinates of the rectangles always integers?
    • Can the rectangles degenerate into lines (zero height or width)?
    • Will the coordinates always define valid rectangles (where x1 < x2 and y1 < y2)?
  2. Boundary Cases:
    • How to handle if the rectangles only touch at a point or along the edges?

We will proceed with the assumption that the rectangles are defined with valid coordinates and can assume normal integer constraints.

Code:

public class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // Extracting the coordinates for better readability
        int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
        int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
        
        // To check if rectangles do not overlap, we check:
        // If one rectangle is on the left side of another
        // or one rectangle is above the other
        if (x2 <= x3 || x4 <= x1 || y2 <= y3 || y4 <= y1) {
            return false;
        }
        
        return true;
    }
}

Strategy:

  1. Understanding Overlap:
    • Two rectangles overlap if they are not completely separated horizontally or vertically.
  2. Non-Overlap Conditions:
    • One rectangle is completely to the left of the other (x2 <= x3 or x4 <= x1).
    • One rectangle is completely above the other (y2 <= y3 or y4 <= y1).
  3. Overlap Condition:
    • Two rectangles overlap if all the above non-overlap conditions are false.

Time Complexity:

The provided solution checks a constant number of conditions using a fixed number of operations (comparisons). Therefore, the time complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI