LeetCode 733 - Flood Fill

The problem is asking us to simulate a flood fill operation on a 2D grid that represents an image. Each cell in the grid contains an integer representing a pixel color. You are given a starting pixel (sr, sc) and a target color color.

leetcodeeasyarraydepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 733

Difficulty: 🟢 Easy
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem is asking us to simulate a flood fill operation on a 2D grid that represents an image. Each cell in the grid contains an integer representing a pixel color. You are given a starting pixel (sr, sc) and a target color color. The goal is to change the color of the starting pixel and all connected pixels of the same original color to the new color. Connection is defined only in the four cardinal directions (up, down, left, right), not diagonally.

The input consists of the image grid image, the starting row sr, the starting column sc, and the new color. The output is the modified image after performing the flood fill.

Constraints tell us that the image can be at most 50x50, which is relatively small, and pixel values are non-negative integers less than 216. This means we can use DFS or BFS without worrying about recursion depth or memory overflow in most languages.

Important edge cases include:

  • The starting pixel is already the target color. Flood fill should not loop infinitely or unnecessarily overwrite pixels.
  • The image contains isolated pixels of the starting color that are not connected; these should remain unchanged.
  • Minimum size images like 1x1 should be handled gracefully.

Approaches

Brute Force Approach

A naive approach would be to scan the entire image, and for each pixel with the original starting color, recursively check all neighbors and update their color. While this would eventually fill the correct area, it is inefficient because it does not efficiently track visited pixels and may revisit pixels multiple times, leading to unnecessary computations.

Optimal Approach

The optimal approach leverages Depth-First Search (DFS) or Breadth-First Search (BFS). Starting from the given pixel (sr, sc), we can explore connected pixels of the same color recursively (DFS) or iteratively (BFS). The key insight is to stop recursion or iteration when a pixel does not match the original color or is out of bounds. Additionally, if the starting pixel already has the target color, we can return the image immediately, avoiding redundant operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n) Scans every pixel, may revisit many times
Optimal (DFS/BFS) O(m * n) O(m * n) Visits only connected pixels of the same color once

Algorithm Walkthrough

  1. Retrieve the original color at the starting pixel (sr, sc). If it is already equal to the target color, return the image immediately.
  2. Define a helper function dfs(r, c) that will perform a recursive DFS. This function will:
  • Check if (r, c) is out of bounds. If so, return.
  • Check if the pixel at (r, c) is the original color. If not, return.
  • Update the pixel at (r, c) to the new color.
  • Recursively call dfs for each of the four neighbors: up (r-1, c), down (r+1, c), left (r, c-1), right (r, c+1).
  1. Start the DFS by calling dfs(sr, sc).
  2. Return the modified image.

Why it works: The DFS ensures that every pixel connected to the starting pixel by the same original color is visited exactly once and updated. The invariant is that after visiting a pixel, all reachable pixels of the original color from that pixel will also eventually be visited and updated.

Python Solution

from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image
        
        def dfs(r: int, c: int):
            if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]):
                return
            if image[r][c] != original_color:
                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

Implementation walkthrough: We first check if the starting pixel is already the target color. The dfs function handles bounds and color checks before updating the pixel and recursively visiting neighbors. This ensures only the connected pixels of the same original color are updated. After recursion completes, the modified image is returned.

Go Solution

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    originalColor := image[sr][sc]
    if originalColor == color {
        return image
    }
    
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
            return
        }
        if image[r][c] != originalColor {
            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
}

Go-specific notes: Go uses function variables for recursion (var dfs func(...)). Bounds and color checks are identical to Python. Slice indexing handles the matrix naturally. The main difference is explicit declaration of function type and the syntax for recursion.

Worked Examples

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Original color at (1,1) is 1. DFS starts at (1,1):

Step-by-step filling:

Step Pixel Updated Image State
1 (1,1) [[1,1,1],[1,2,0],[1,0,1]]
2 (0,1) [[1,2,1],[1,2,0],[1,0,1]]
3 (0,0) [[2,2,1],[1,2,0],[1,0,1]]
4 (1,0) [[2,2,1],[2,2,0],[1,0,1]]
5 (0,2) [[2,2,2],[2,2,0],[1,0,1]]

Final result: [[2,2,2],[2,2,0],[2,0,1]].

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Original color equals target color, so the function returns the image immediately.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) In the worst case, DFS visits every pixel once.
Space O(m * n) DFS recursion stack can go as deep as all pixels in a connected component.

Even though the recursion stack can be large, the constraints of m, n <= 50 make it safe.

Test Cases

# test cases
sol = Solution()

# Provided examples
assert sol.floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2) == [[2,2,2],[2,2,0],[2,0,1]]  # fills center component
assert sol.floodFill([[0,0,0],[0,0,0]], 0, 0, 0) == [[0,0,0],[0,0,0]]  # no change, same color

# Edge cases
assert sol.floodFill([[1]], 0, 0, 2) == [[2]]  # single pixel
assert sol.floodFill([[1,2],[2,1]], 0, 0, 3) == [[3,2],[2,1]]  # only connected pixels filled
assert sol.floodFill([[1,1,1],[1,1,1],[1,1,1]], 1, 1, 1) == [[1,1,1],[1,1,1],[1,1,1]]  # no-op, same color
Test Why
[[1,1,1],[1,1,0],[1,0,1]] Verifies DFS spreads correctly in connected component
[[0,0,0],[0,0,0]] Starting pixel already target color
[[1]] Single pixel edge case
[[1,2],[2,1]] Only fill connected pixels of same color
[[1,1,1],[1,1,1],[1,1,1]] Flood fill no-op when color is the same

Edge Cases

  1. Starting pixel already has target color: This can