Problem

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

Examples

Example 1:

1
2
3
4
5

Input:
rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output:
 true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

1
2
3
4
5

Input:
rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output:
 false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

1
2
3
4
5

Input:
rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output:
 false
Explanation: Because two of the rectangles overlap with each other.

Solution

Method 1 – Area and Corner Set Check

Intuition

To form a perfect rectangle cover, the total area of all rectangles must equal the area of the bounding rectangle, and every corner must appear an even number of times except for the four corners of the bounding rectangle, which must appear exactly once.

Approach

  1. Track the min and max x and y to get the bounding rectangle.
  2. For each rectangle, add its area to a total and update a set with its four corners (add if not present, remove if present).
  3. After processing all rectangles, check:
    • The total area equals the area of the bounding rectangle.
    • The set contains exactly four points, which are the corners of the bounding rectangle.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rects) {
        set<pair<int,int>> s;
        int minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;
        long area = 0;
        for (auto& r : rects) {
            minx = min(minx, r[0]); miny = min(miny, r[1]);
            maxx = max(maxx, r[2]); maxy = max(maxy, r[3]);
            area += (long)(r[2]-r[0])*(r[3]-r[1]);
            vector<pair<int,int>> pts = {{r[0],r[1]},{r[0],r[3]},{r[2],r[1]},{r[2],r[3]}};
            for (auto& p : pts) {
                if (!s.insert(p).second) s.erase(p);
            }
        }
        if (area != (long)(maxx-minx)*(maxy-miny)) return false;
        if (s.size() != 4) return false;
        if (!s.count({minx,miny}) || !s.count({minx,maxy}) || !s.count({maxx,miny}) || !s.count({maxx,maxy})) return false;
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isRectangleCover(rects [][]int) bool {
    minx, miny, maxx, maxy := 1<<31-1, 1<<31-1, -1<<31, -1<<31
    area := 0
    s := map[[2]int]bool{}
    for _, r := range rects {
        minx = min(minx, r[0]); miny = min(miny, r[1])
        maxx = max(maxx, r[2]); maxy = max(maxy, r[3])
        area += (r[2]-r[0])*(r[3]-r[1])
        pts := [][2]int{{r[0],r[1]},{r[0],r[3]},{r[2],r[1]},{r[2],r[3]}}
        for _, p := range pts {
            if s[p] { delete(s, p) } else { s[p] = true }
        }
    }
    if area != (maxx-minx)*(maxy-miny) { return false }
    if len(s) != 4 { return false }
    for _, p := range [][2]int{{minx,miny},{minx,maxy},{maxx,miny},{maxx,maxy}} {
        if !s[p] { return false }
    }
    return true
}
func min(a, b int) int { if a < b { return a } else { return b } }
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public boolean isRectangleCover(int[][] rects) {
        Set<String> s = new HashSet<>();
        int minx = Integer.MAX_VALUE, miny = Integer.MAX_VALUE, maxx = Integer.MIN_VALUE, maxy = Integer.MIN_VALUE;
        long area = 0;
        for (int[] r : rects) {
            minx = Math.min(minx, r[0]); miny = Math.min(miny, r[1]);
            maxx = Math.max(maxx, r[2]); maxy = Math.max(maxy, r[3]);
            area += (long)(r[2]-r[0])*(r[3]-r[1]);
            String[] pts = {r[0]+" "+r[1], r[0]+" "+r[3], r[2]+" "+r[1], r[2]+" "+r[3]};
            for (String p : pts) {
                if (!s.add(p)) s.remove(p);
            }
        }
        if (area != (long)(maxx-minx)*(maxy-miny)) return false;
        if (s.size() != 4) return false;
        if (!s.contains(minx+" "+miny) || !s.contains(minx+" "+maxy) || !s.contains(maxx+" "+miny) || !s.contains(maxx+" "+maxy)) return false;
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun isRectangleCover(rects: Array<IntArray>): Boolean {
        var minx = Int.MAX_VALUE; var miny = Int.MAX_VALUE
        var maxx = Int.MIN_VALUE; var maxy = Int.MIN_VALUE
        var area = 0L
        val s = mutableSetOf<Pair<Int,Int>>()
        for (r in rects) {
            minx = minOf(minx, r[0]); miny = minOf(miny, r[1])
            maxx = maxOf(maxx, r[2]); maxy = maxOf(maxy, r[3])
            area += (r[2]-r[0]).toLong()*(r[3]-r[1])
            val pts = listOf(r[0] to r[1], r[0] to r[3], r[2] to r[1], r[2] to r[3])
            for (p in pts) if (!s.add(p)) s.remove(p)
        }
        if (area != (maxx-minx).toLong()*(maxy-miny)) return false
        if (s.size != 4) return false
        if (!s.contains(minx to miny) || !s.contains(minx to maxy) || !s.contains(maxx to miny) || !s.contains(maxx to maxy)) return false
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def isRectangleCover(self, rects: list[list[int]]) -> bool:
        minx = miny = float('inf')
        maxx = maxy = float('-inf')
        area = 0
        s = set()
        for r in rects:
            minx = min(minx, r[0]); miny = min(miny, r[1])
            maxx = max(maxx, r[2]); maxy = max(maxy, r[3])
            area += (r[2]-r[0])*(r[3]-r[1])
            pts = [(r[0],r[1]), (r[0],r[3]), (r[2],r[1]), (r[2],r[3])]
            for p in pts:
                if p in s: s.remove(p)
                else: s.add(p)
        if area != (maxx-minx)*(maxy-miny): return False
        if len(s) != 4: return False
        if (minx,miny) not in s or (minx,maxy) not in s or (maxx,miny) not in s or (maxx,maxy) not in s: return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::HashSet;
impl Solution {
    pub fn is_rectangle_cover(rects: Vec<Vec<i32>>) -> bool {
        let (mut minx, mut miny, mut maxx, mut maxy) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
        let mut area = 0;
        let mut s = HashSet::new();
        for r in &rects {
            minx = minx.min(r[0]); miny = miny.min(r[1]);
            maxx = maxx.max(r[2]); maxy = maxy.max(r[3]);
            area += (r[2]-r[0])*(r[3]-r[1]);
            let pts = [(r[0],r[1]), (r[0],r[3]), (r[2],r[1]), (r[2],r[3])];
            for &p in &pts {
                if !s.insert(p) { s.remove(&p); }
            }
        }
        if area != (maxx-minx)*(maxy-miny) { return false; }
        if s.len() != 4 { return false; }
        if !s.contains(&(minx,miny)) || !s.contains(&(minx,maxy)) || !s.contains(&(maxx,miny)) || !s.contains(&(maxx,maxy)) { return false; }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    isRectangleCover(rects: number[][]): boolean {
        let minx = Infinity, miny = Infinity, maxx = -Infinity, maxy = -Infinity, area = 0;
        const s = new Set<string>();
        for (const r of rects) {
            minx = Math.min(minx, r[0]); miny = Math.min(miny, r[1]);
            maxx = Math.max(maxx, r[2]); maxy = Math.max(maxy, r[3]);
            area += (r[2]-r[0])*(r[3]-r[1]);
            const pts = [[r[0],r[1]],[r[0],r[3]],[r[2],r[1]],[r[2],r[3]]];
            for (const p of pts) {
                const key = p.join(',');
                if (s.has(key)) s.delete(key); else s.add(key);
            }
        }
        if (area !== (maxx-minx)*(maxy-miny)) return false;
        if (s.size !== 4) return false;
        if (!s.has([minx,miny].join(',')) || !s.has([minx,maxy].join(',')) || !s.has([maxx,miny].join(',')) || !s.has([maxx,maxy].join(','))) return false;
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of rectangles.
  • 🧺 Space complexity: O(n), for the set of corners.