# 6 lines O(n) Python

• 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[0] + outer[-1]
return sum((d-b)*(c-a) for a,b,c,d in rect) == (up-bottom)*(right-left)
``````

• How is your solution O(n) when you're sorting?

• @livelearn
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.

• @realisking
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.