There's no need to use a Queue (or Deque in python) for most BFS solutions
joeleetcode2018
189

Using a plain list in python is much less expensive:

Look at this BFS solution for flood fill.

class Solution:
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        
        Time: O(R*C)
        Space: O(R*C)
        """        
        q = [(sr,sc)]
        currColor = image[sr][sc]  
        if currColor == newColor:
            return image
        while q:
            newQ=[]
            for r,c in q:                
                image[r][c] = newColor               
                for d in [(1,0),(-1,0),(0,1),(0,-1)]:
                    newR,newC = r+d[0],c+d[1]
                    if 0<=newR<len(image) and 0<=newC<len(image[0]) and image[newR][newC]==currColor:
                        newR,newC = r+d[0],c+d[1]
                        newQ.append((newR,newC))
            q=newQ
        return image
Comments (1)