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.
Example 1:
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:
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:
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.
Constraints:
1 <= rectangles.length <= 2 * 10^4rectangles[i].length == 4-10^5 <= xi, yi, ai, bi <= 10^5
Solution
/**
* @param {number[][]} rectangles
* @return {boolean}
*/
var isRectangleCover = function(rectangles) {
let tls = new Set
let trs = new Set
let bls = new Set
let brs = new Set
for (let [l, b, r, t] of rectangles) {
let tl = corner(t, l)
let tr = corner(t, r)
let bl = corner(b, l)
let br = corner(b, r)
if (tls.has(tl) || trs.has(tr) || bls.has(bl) || brs.has(br)) return false
if (!bls.delete(tl) && !trs.delete(tl)) tls.add(tl)
if (!brs.delete(tr) && !tls.delete(tr)) trs.add(tr)
if (!brs.delete(bl) && !tls.delete(bl)) bls.add(bl)
if (!bls.delete(br) && !trs.delete(br)) brs.add(br)
}
return tls.size === 1 && trs.size === 1 && bls.size === 1 && brs.size === 1
};
let corner = (x, y) => `${ x } ${ y }`
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).