391. Perfect Rectangle

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.

Example1:

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.

Example2:

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.

Example3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
Output: false
Explanation: Because there is a gap in the top center.

Example4:

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 * 10000
rectangles[i].length == 4
-100000 <= xi, yi, ai, bi <= 100000

Problem Summary

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

If all the rectangles together exactly cover a certain rectangular region, return true; otherwise, return false.

Solution Approach

If the area of the rectangular region equals the sum of the areas of all rectangles, and the four corner vertices of the rectangular region each appear exactly once, while all other vertices appear only two or four times, then return true; otherwise, return false.

Code


package leetcode

type point struct {
	x int
	y int
}

func isRectangleCover(rectangles [][]int) bool {
	minX, minY, maxA, maxB := rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
	area := 0
	cnt := make(map[point]int)
	for _, v := range rectangles {
		x, y, a, b := v[0], v[1], v[2], v[3]
		area += (a - x) * (b - y)
		minX = min(minX, x)
		minY = min(minY, y)
		maxA = max(maxA, a)
		maxB = max(maxB, b)
		cnt[point{x, y}]++
		cnt[point{a, b}]++
		cnt[point{x, b}]++
		cnt[point{a, y}]++
	}
	if area != (maxA - minX) * (maxB - minY) ||
		cnt[point{minX, minY}] != 1 || cnt[point{maxA, maxB}] != 1 ||
		cnt[point{minX, maxB}] != 1 || cnt[point{maxA, minY}] != 1 {
		return false
	}
	delete(cnt, point{minX, minY})
	delete(cnt, point{maxA, maxB})
	delete(cnt, point{minX, maxB})
	delete(cnt, point{maxA, minY})
	for _, v := range cnt {
		if v != 2 && v != 4 {
			return false
		}
	}
	return true
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}