Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Flood Fill

On This Page

Problem Statement

Why this is an Island problem

Solution

Code (DFS)

Time Complexity

Space Complexity

Problem Statement

Any image can be represented by a 2D integer array (i.e., a matrix) where each cell represents the pixel value of the image.

Flood fill algorithm takes a starting cell (i.e., a pixel) and a color. The given color is applied to all horizontally and vertically connected cells with the same color as that of the starting cell. Recursively, the algorithm fills cells with the new color until it encounters a cell with a different color than the starting cell.

Given a matrix, a starting cell, and a color, flood fill the matrix.

Example 1:

Input: matrix =

starting cell = (1, 3)
new color = 2

Output:

Example 2:

Input: matrix =

starting cell = (3, 2)

new color = 5

Output:

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 50
0 <= matrix[i][j], color < 2<sup>16</sup>
0 <= x < m
0 <= y < n

Why this is an Island problem

What the question says	The signal it matches
"represented by a 2D integer array"	the input is a two dimensional grid of cells
"all horizontally and vertically connected cells"	cells are joined to their neighbours by position
"Flood fill algorithm takes a starting cell"	the wording includes flood

This is the repaint a region variant: the traversal writes a new value as it goes.

The closest alternative. There is none. This is the pattern at its plainest: one region, one traversal, no counting.

The repaint itself does the bookkeeping. A repainted cell no longer has "the same color as that of the starting cell". The traversal never re-enters it, and no separate visited structure is needed. That shortcut hides one trap. If the new color equals the starting color, repainting changes nothing, and the traversal re-enters cells forever. Check that one case before starting, and return the matrix unchanged.

Solution

The question follows the Island pattern and is quite similar to Number of Islands problem.

From the given starting cell, we can perform a Depth First Search (DFS) or Breadth First Search (BFS) to find all of its connected cells with the same color. During our DFS or BFS traversal, we will update the cells with the new color.

Following is the DFS or BFS traversal of the example-2 mentioned above:

Code (DFS)

Here is what our DFS algorithm will look like:

Python3

. . . .

Time Complexity

The time complexity of the above algorithm will be $O(M*N)$ , where M is the number of rows and 'N' is the number of columns of the input matrix. This is because, in the worst case, we might have to fill the whole matrix.

Space Complexity

DFS recursion stack can go $M*N$ deep when we have to fill the whole matrix. Hence, the space complexity will be $O(M*N)$ , where M is the number of rows and 'N' is the number of columns of the input matrix.

Mark as Completed

Luis Roel

· 3 years ago

class Solution:
  def floodFill(self, matrix, x, y, newColor):
    startingColor = matrix[x][y]
    seen = set()

    def go(x, y):
      if (x, y) in seen:
        return
      
      if x < 0 or x >= len(matrix):
        return
      if y < 0 or y >= len(matrix[0]):
        return
      
      seen.add((x, y))

      if matrix[x][y] != startingColor:
        return

      matrix[x][y] = newColor

      go(x + 1, y)
      go(x - 1, y)
      go(x, y + 1)
      go(x, y - 1)

    go(x, y)
    
    return matrix

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def floodFill(self, matrix, x, y, newColor):
    # TODO: Write your code here
    # BFS solution, we can use visited to mark the visited cell then rewrite it with color
    # for row in range(len(matrix)):
    #   for col in range(len(matrix[0])):
    # self.visitCellBFS(matrix, x, y, newColor)
    self.visitCellDFS(x, y, matrix, matrix[x][y], newColor)
    return matrix
  def visitCellBFS(self, matrix, row, col, newColor):
    neighbors = deque([(row, col)])
    oldColor = matrix[row][col]
    visited_list = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

    while neighbors:
      row, col = neighbors.popleft()

      if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
        continue

Elaine Michelle Teh

· 4 years ago

Show 3 replies

Mitch

· 4 years ago

Show 4 replies

Reading Progress

Vote for new content

On This Page

Problem Statement

Why this is an Island problem

Solution

Code (DFS)

Time Complexity

Space Complexity