algoadvance

Leetcode 836. Rectangle Overlap

Problem Statement:

You are given two axis-aligned rectangles rec1 and rec2, represented as lists of 4 integers [x1, y1, x2, y2], where (x1, y1) represents the bottom-left corner and (x2, y2) represents the top-right corner of the rectangle. Write a function to determine if these two rectangles overlap.

Rectangles overlap when there is a non-empty rectangle that is covered by both rectangles.

Return true if they overlap, otherwise return false.

Clarifying Questions:

  1. Input Characteristics:
    • What are the integer ranges for the coordinates of the rectangles?
    • Is it safe to assume all coordinates fall within standard integer boundaries?
  2. Edge Cases:
    • What should be the return value if the rectangles just touch at one edge or corner (considered overlap)?
    • Can either or both rectangles be degenerate (i.e., represent a line or point)?

Strategy:

To determine if two rectangles overlap, we can use the principle that two rectangles do not overlap if one is entirely to the left, right, above, or below the other rectangle.

Given rec1 = [x1, y1, x2, y2] and rec2 = [x1', y1', x2', y2']:

If none of the above conditions are true, the rectangles must overlap.

Code:

#include <vector>

using namespace std;

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        // Check if one rectangle is to the left of the other
        if (rec1[2] <= rec2[0] || rec2[2] <= rec1[0]) {
            return false;
        }
        // Check if one rectangle is above the other
        if (rec1[3] <= rec2[1] || rec2[3] <= rec1[1]) {
            return false;
        }
        return true;
    }
};

Time Complexity:

The time complexity of this solution is O(1) because we are only performing a fixed number of comparison operations, regardless of the size or position of the rectangles. This makes the solution very efficient.

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