O(nOfBlackPixels) time, best BFS solution in Python with detailed explanation


  • 0
    Y
    class Solution(object):
        def minArea(self, image, x, y):
            """
            :type image: List[List[str]]
            :type x: int
            :type y: int
            :rtype: int
            """
            top, left = float("inf"), float("inf")
            bot, right = -1, -1
            
            image[x][y] = None
            q = collections.deque([(x, y)])
            while q:
                x, y = q.pop()
                top, left = min(x, top), min(y, left)
                bot, right = max(x, bot), max(y, right)
                for x0, y0 in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
                    if 0 <= x0 < len(image) and 0 <= y0 < len(image[0]) and image[x0][y0] == "1":
                        image[x0][y0] = None
                        q.appendleft((x0, y0))
            return (right - left + 1) * (bot - top + 1)
    

    Many people will have the question: whey do we need x and y here ?
    The reason is, instead of O(mn) time, where the image can be very big, we only need O(nOfPixel) Time if we have x ,y, we do BFS and found the topLeft corner and botRight corner of this rectangle, top is the smallest x value ever observed in BFS, left is the smalles y value, similar for bot and right.
    Then, we got our rectangle after one BFS, wow, is this amazing :)


Log in to reply
 

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