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 == - m == matrix[i].length
• 1 <= m, n <= 50
• 0 <= - m == matrix[i][j], color < 2¹⁶
• 0 <= x < m
• 0 <= y < n

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:

Time Complexity

Time complexity 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 due to the fact that, 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.