Flood Fill

Difficulty: Easy | Acceptance: 68.20% | Paid: No Topics: Array, Depth-First Search, Breadth-First Search, Matrix

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 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.

• Examples
• Constraints
• DFS (Recursive)
• BFS (Iterative)
• DFS (Iterative with Stack)

Examples

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.

Constraints

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 2¹⁶
0 <= sr < m
0 <= sc < n

DFS (Recursive)

Intuition Use recursion to explore all 4-directionally connected pixels that have the same color as the starting pixel, and change them to the new color.

Steps

• Check if the starting pixel’s color is already the target color to avoid infinite recursion
• Define a recursive function that takes row and column as parameters
• Base case: if out of bounds or pixel color doesn’t match original color, return
• Change the current pixel’s color to the new color
• Recursively call the function on all 4 neighbors

from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        
        m, n = len(image), len(image[0])
        
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != original:
                return
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        dfs(sr, sc)
        return image

Complexity

• Time: O(m × n) where m is the number of rows and n is the number of columns
• Space: O(m × n) in the worst case due to recursion stack depth
• Notes: Simple and elegant, but may cause stack overflow for very large images

BFS (Iterative)

Intuition Use a queue to explore pixels level by level, starting from the given pixel and expanding to all 4-directionally connected neighbors with the same color.

Steps

• Check if the starting pixel’s color is already the target color
• Initialize a queue with the starting position
• While the queue is not empty, dequeue a position
• Change the pixel’s color and add all valid 4-directional neighbors with the original color to the queue

from typing import List
from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        
        m, n = len(image), len(image[0])
        queue = deque([(sr, sc)])
        
        while queue:
            r, c = queue.popleft()
            if image[r][c] != original:
                continue
            image[r][c] = color
            if r + 1 < m:
                queue.append((r + 1, c))
            if r - 1 >= 0:
                queue.append((r - 1, c))
            if c + 1 < n:
                queue.append((r, c + 1))
            if c - 1 >= 0:
                queue.append((r, c - 1))
        
        return image

Complexity

• Time: O(m × n) where m is the number of rows and n is the number of columns
• Space: O(m × n) in the worst case for the queue
• Notes: Avoids stack overflow issues of recursive DFS, but uses more memory for the queue

DFS (Iterative with Stack)

Intuition Simulate the recursive DFS using an explicit stack data structure to avoid potential stack overflow while maintaining the depth-first exploration pattern.

Steps

• Check if the starting pixel’s color is already the target color
• Initialize a stack with the starting position
• While the stack is not empty, pop a position
• Change the pixel’s color and push all valid 4-directional neighbors with the original color to the stack

from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        
        m, n = len(image), len(image[0])
        stack = [(sr, sc)]
        
        while stack:
            r, c = stack.pop()
            if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != original:
                continue
            image[r][c] = color
            stack.append((r + 1, c))
            stack.append((r - 1, c))
            stack.append((r, c + 1))
            stack.append((r, c - 1))
        
        return image

Complexity

• Time: O(m × n) where m is the number of rows and n is the number of columns
• Space: O(m × n) in the worst case for the stack
• Notes: Avoids recursion stack overflow while maintaining DFS behavior