Leetcode 391. Perfect Rectangle

Problem Explanation

Given N axis-aligned rectangles, the problem is to determine whether they together form a perfect rectangle. That is, if we rearrange the given rectangles, whether it forms a single complete rectangle without any overlap or not. Each rectangle is represented by the coordinates of its bottom-left and top-right points.

For example: For the set of rectangles, say [{1,1,3,4}, {3,1,4,4}], it would form an exact rectangle cover. But for the set of rectangles [{1,1,2,3}, {1,3,2,4}, {3,1,4,2}], it could not form a perfect rectangle due to overlap or missing areas.

Solution Approach

The underlying principle in this solution is to track the area and corners of all the rectangles. By totaling the area of all the rectangles, it should be equal to the area of the smallest possible rectangle that encompasses all the rectangles (the bounding box) if they form a complete rectangle cover. Also, only the four corners of this bounding box should be present exactly once in the set of corners we accumulate, which means there should be no overlaps or gaps.

The solution works as follows:

1. Initiate variables to hold the area of all rectangles, as well as the coordinates of the 2 points that define the overall covering rectangle (a bottom-left and a top-right point).

2. Crop through each rectangle in the list.

3. For each rectangle, calculate it's area and add it to the total area. Then check and update the bottom-left and top-right points if needed.

4. For each rectangle, add the corners to a set. If a corner already exists in the set, it means that it is shared by multiple rectangles so remove it.

5. After cropping through the rectangles, calculate the area of the overall rectangle and compare it to the total area of all rectangles.

6. Also, check that the set of corners has exactly 4 corners and they match the corners of the overall rectangle.

7. If the areas match and the corners check pass, return true. Otherwise, return false.

A key data structure used in the solution is a hashSet to store corners. The solution uses properties of geometric rectangles.

Example Walkthrough

For example, let’s say the given rectangles are [{1,1,3,4}, {3,1,4,4}].

1. First we initialize our variables: area = 0, x1 = INT_MAX, y1 = INT_MAX, x2 = INT_MIN, y2 = INT_MIN, corners = empty hashSet.

2. Looping through the rectangles, for first rectangle {1,1,3,4}, we compute its area as 6 and add it to the area variable. We update our x1 = 1, y1 = 1, x2 = 3, y2 = 4. We attempt to add all 4 corners of this rectangle to the corners hashSet.

3. For the second rectangle {3,1,4,4}, we compute its area as 3 and add it to the area variable. We update our x1 = 1, y1 = 1, x2 = 4, y2 = 4. We attempt to add all 4 corners of this rectangle to the corners hashSet.

4. For all rectangles, total area comes out to be 9 which exactly equals the area of overall rectangle (3x3=9).

5. Twisting the corners hashSet, we get only 4 corners which are four corners of the overall rectangle.

6. Hence, it returns true which means this set of rectangles can form an exact rectangle cover.

Python Solution

1
2python
3class Solution:
4    def isRectangleCover(self, rectangles):
5        area = 0
6        x1 = float('inf')
7        y1 = float('inf')
8        x2 = float('-inf')
9        y2 = float('-inf')
10        corners = set()
11
12        for x1_, y1_, x2_, y2_ in rectangles:
13            area += (x2_ - x1_) * (y2_ - y1_)
14            x1 = min(x1, x1_)
15            y1 = min(y1, y1_)
16            x2 = max(x2, x2_)
17            y2 = max(y2, y2_)
18
19            for p in [(x1_, y1_), (x1_, y2_), (x2_, y1_), (x2_, y2_)]: 
20                if p in corners:
21                    corners.remove(p)
22                else:
23                    corners.add(p)
24
25        if len(corners) != 4 or {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} != corners:
26            return False
27        return area == (x2 - x1) * (y2 - y1)

For complementary Java, JavaScript, C++ and C# solutions to this problem, you can visit this Link. Please remember that understanding the problem and the method to solve it is more important than specific language syntax.

Java Solution

1
2java
3public class Solution {
4    public boolean isRectangleCover(int[][] rectangles) {
5        Set<String> set = new HashSet<>();
6        int area = 0;
7        int x1 = Integer.MAX_VALUE, y1 = Integer.MAX_VALUE, x2 = Integer.MIN_VALUE, y2 = Integer.MIN_VALUE;
8        
9        for (int[] rect : rectangles) {
10            x1 = Math.min(rect[0], x1);
11            y1 = Math.min(rect[1], y1);
12            x2 = Math.max(rect[2], x2);
13            y2 = Math.max(rect[3], y2);
14            
15            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
16            
17            String s1 = rect[0] + " " + rect[1];
18            String s2 = rect[0] + " " + rect[3];
19            String s3 = rect[2] + " " + rect[3];
20            String s4 = rect[2] + " " + rect[1];
21            
22            if (!set.add(s1)) set.remove(s1);
23            if (!set.add(s2)) set.remove(s2);
24            if (!set.add(s3)) set.remove(s3);
25            if (!set.add(s4)) set.remove(s4);
26        }
27        
28        if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) 
29            return false;
30       
31        return area == (x2-x1) * (y2-y1);
32    }
33}

JavaScript Solution

1
2javascript
3var isRectangleCover = function(rectangles) {
4    let area = 0;
5    let [x1, y1, x2, y2] = [Number.MAX_VALUE, Number.MAX_VALUE, Number.MIN_VALUE, Number.MIN_VALUE];
6    let corners = new Set();
7
8    for (let [x1_, y1_, x2_, y2_] of rectangles) {
9        area += (x2_ - x1_) * (y2_ - y1_);
10        x1 = Math.min(x1, x1_);
11        y1 = Math.min(y1, y1_);
12        x2 = Math.max(x2, x2_);
13        y2 = Math.max(y2, y2_);
14
15        for (let p of [[x1_, y1_], [x1_, y2_], [x2_, y1_], [x2_, y2_]]) {
16            let key = p.join(',')
17            if (corners.has(key)) {
18                corners.delete(key);
19            } else {
20                corners.add(key);
21            }
22        }
23    }
24
25    if (corners.size !== 4 || !corners.has([x1, y1].join(',')) || !corners.has([x1, y2].join(',')) || !corners.has([x2, y1].join(',')) || !corners.has([x2, y2].join(','))) 
26        return false;
27
28    return area === (x2 - x1) * (y2 - y1);
29};

In both the Java and JavaScript solutions, we encode the points (or corners) as strings to be stored in a Set data structure. The JavaScript solution essentially mirrors the Python algorithm, but includes conversions to and from strings for data manipulation.

These are great starting points for understanding how to approach problems involving rectangles and their properties. Keep practicing for further understanding and to learn more complex algorithms.