6 lines O(n) Python


  • 0

    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)
    

  • 0
    L

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


  • 0

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


  • 0
    L

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

    Think about the case [[1,1,2,2],[3,3,4,4],[5,5,6,6],[7,7,8,8],[9,9,10,10]]


  • 0

    @livelearn
    Aha, you are correct, thanks for point that out. Let me rewrite it a little bit to make it still O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.