After some observation, I find for every
true case, we have and only have 4 boundary points which appear only once. These points are the outmost point of our big rectangle. Then, we only need to check whether the sum of area for each small rectangle equals to the big rectangle. One more thing to keep in mind is we're not allowed to have duplicated small rectangles at the beginning, and that's it.
class Solution(object): def isRectangleCover(self, rect): """ :type rect: List[List[int]] :rtype: bool """ if len(rect) > len(set(map(tuple, rect))): return False count = collections.Counter(pos for a,b,c,d in rect for pos in ((a,b), (a,d), (c,b), (c,d))) outer = [pos for pos in count if count[pos] == 1] if len(outer) != 4: return False outer.sort() left, bottom, right, up = outer + outer[-1] return sum((d-b)*(c-a) for a,b,c,d in rect) == (up-bottom)*(right-left)
As I've mentioned in the first line of my original post. "For every true case, we have and only have 4 boundary points which appear only once". The
outer only has 4 tuples, thus yes, my solution is O(n) when I'm sorting.
What if I was given a bunch of rectangles that never overlapped? It would not return False in the first line because the len(rect)=len(set(map(tuple,rect))). Your sorted would be taking in a big input of positions.
Think about the case [[1,1,2,2],[3,3,4,4],[5,5,6,6],[7,7,8,8],[9,9,10,10]]
Aha, you are correct, thanks for point that out. Let me rewrite it a little bit to make it still O(n).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.