🌊733. Flood Fill

Easy | Grind 75 | August 23 Tuesday, 2022

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Constraints:

• m == image.length

• n == image[i].length

• 1 <= m, n <= 50

• 0 <= image[i][j], color < 216

• 0 <= sr < m

• 0 <= sc < n

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) 
(i.e., the red pixel), all pixels connected by a path of the same color as 
the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally
 connected to the starting pixel.

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: The starting pixel is already colored 0, so no changes are made 
to the image.

SOLUTION

Starting from the given index [sr][sc], check if the target color is the same as the value of the start index. If they are different, add the current start index and its value to a queue. Otherwise, your code should return the original list. Pop from the queue to get the start index and its value. Check the four (left, right, up, down) neighbors of the start index. If the neighbors have the same value as the start element, put their indices in the queue to be processed later. Afterwards, change the value of the current index to the target value (color). Now, pop another element from the queue and repeat the process.

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # directions    up    right   down   left
        directions = [(-1,0), (0,1), (1,0), (0,-1)]
        
        # store the elements that can be changed
        queue = deque()
        
        # the start element shouldn't be the target color
        if image[sr][sc] != color: 
            queue.append((image[sr][sc],sr,sc))
            
        # length and height of the list
        length, height = len(image), len(image[0])
        
        # we iterate until there are no more elements left to be changed
        while queue: 
            curr = queue.pop()
            
            for pos in directions: 
                row, col = curr[1]+pos[0], curr[2]+pos[1]
                # make sure the connected(left, right,up, down) index is within the list
                if 0 <= row < length and 0 <= col < height: 
                    # if element at index is the same as starting element, we can change it to target so put in queue
                    if image[row][col] == curr[0]: 
                        queue.append((image[row][col], row, col))
                        
            # change the current element value to target value
            image[curr[1]][curr[2]] = color
        
        return image
        
        

TIME AND SPACE COMPLEXITY

TIME: O(NxM) where n is the length of the list and M is the height of M. In the worst case, we will have to iterate and process every single element in the list. The total number of element is NxM. Hence the runtime of O(NxM)

SPACE: O(NxM) in the worst, we will store close to NxM elements.