Check if any pair of rectangles overlap

Problem

You are given given a list of rectangles represented by min and max x- and y-coordinates. Compute whether or not a pair of rectangles overlap each other. If one rectangle completely covers another, it is considered overlapping.

Examples

Example 1

Input:  rectangles = [{
    "top_left": [1, 4],
    "dimensions": [3, 3] # width, height
},
{
    "top_left": [-1, 3],
    "dimensions": [2, 1]
},
{
    "top_left": [0, 5],
    "dimensions": [4, 3]
}]
Output: true
Explanation:
The first rectangle (from (1,4) to (4,1)) and the third rectangle (from (0,5) to (4,2)) overlap.

Solution

Method 1 - Check if 2 Rectangles overlap in pairs

We have already seen [Rectangle Overlap](rectangle-overlap). We can reuse that solution and solve this problem.

To determine if any pair of rectangles overlap, we need to check if there's any intersecting region between each pair of rectangles:

1. Extract the coordinates of two rectangles.
2. Check if one rectangle is completely to the left, right, above, or below the other.
3. If none of these conditions are met, then the rectangles overlap.

Approach

1. Extract Rectangle Edges: Identify the coordinates of the bottom-right corner using the top-left corner and dimensions.
2. Check Overlap: Two rectangles do not overlap if one is completely to the left, right, above, or below the other.
3. Compare All Pairs: Check all pairs of rectangles in the list to see if any pair overlaps.

Code

Java

public class Solution {
    public boolean haveAnyRectanglesOverlap(List<Map<String, List<Integer>>> rectangles) {
        int n = rectangles.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isOverlap(rectangles.get(i), rectangles.get(j))) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isOverlap(Map<String, List<Integer>> rec1, Map<String, List<Integer>> rec2) {
        int x1 = rec1.get("top_left").get(0);
        int y1 = rec1.get("top_left").get(1);
        int x2 = x1 + rec1.get("dimensions").get(0);
        int y2 = y1 - rec1.get("dimensions").get(1);

        int x3 = rec2.get("top_left").get(0);
        int y3 = rec2.get("top_left").get(1);
        int x4 = x3 + rec2.get("dimensions").get(0);
        int y4 = y3 - rec2.get("dimensions").get(1);
        
        // Check if one rectangle is completely to the left, right, above, or below the other
        if (x1 >= x4 || x3 >= x2 || y1 <= y4 || y3 <= y2) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<Map<String, List<Integer>>> rectangles = Arrays.asList(
            Map.of("top_left", Arrays.asList(1, 4), "dimensions", Arrays.asList(3, 3)),
            Map.of("top_left", Arrays.asList(-1, 3), "dimensions", Arrays.asList(2, 1)),
            Map.of("top_left", Arrays.asList(0, 5), "dimensions", Arrays.asList(4, 3))
        );
        System.out.println(sol.haveAnyRectanglesOverlap(rectangles)); // Output: true
    }
}

Python

class Solution:
    def have_any_rectangles_overlap(self, rectangles: List[Dict[str, List[int]]]) -> bool:
        n = len(rectangles)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if self.is_overlap(rectangles[i], rectangles[j]):
                    return True
        return False

    def is_overlap(self, rec1: Dict[str, List[int]], rec2: Dict[str, List[int]]) -> bool:
        x1, y1 = rec1["top_left"]
        w1, h1 = rec1["dimensions"]
        x2, y2 = x1 + w1, y1 - h1
        
        x3, y3 = rec2["top_left"]
        w2, h2 = rec2["dimensions"]
        x4, y4 = x3 + w2, y3 - h2
        
        # Check if one rectangle is completely to the left, right, above, or below the other
        if x1 >= x4 or x3 >= x2 or y1 <= y4 or y3 <= y2:
            return False
        return True

# Example usage
sol = Solution()
rectangles = [
    {"top_left": [1, 4], "dimensions": [3, 3]},
    {"top_left": [-1, 3], "dimensions": [2, 1]},
    {"top_left": [0, 5], "dimensions": [4, 3]}
]
print(sol.have_any_rectangles_overlap(rectangles))  # Output: true

Complexity

• ⏰ Time complexity: O(n^2) where n is the number of rectangles, since every pair of rectangles needs to be checked.
• 🧺 Space complexity: O(1) as no additional data structures are needed except a few variables.