How do you solve Flood Fill on LeetCode?

Flood Fill (LeetCode #733) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding connected components is crucial for flood fill.

What is the brute force solution for Flood Fill?

The brute force approach for Flood Fill is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking each pixel in the image to see if it matches the original color and changing it to the new color. This method is straightforward but inefficient because it may require checking every pixel multiple times. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Flood Fill?

Flood Fill uses the following concepts: Array, Depth-First Search, Breadth-First Search, Matrix. The recommended patterns to study are: Depth-First Search, Breadth-First Search, Recursion.

What are the interview tips for Flood Fill?

Explain your thought process clearly while coding. Consider edge cases like when the starting pixel is already the target color. Practice both recursive and iterative approaches to be versatile.

What are common mistakes when solving Flood Fill?

Not checking if the original color is the same as the new color before starting the fill. Failing to handle out-of-bounds conditions in recursive calls.

#733

Flood Fill

Easy

ArrayDepth-First SearchBreadth-First SearchMatrixDepth-First SearchBreadth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to explore and change the color of connected pixels recursively or iteratively. This method is efficient as it only processes each pixel once.

⚙️

Algorithm

3 steps

1Step 1: Define a helper function that checks if a pixel is valid (within bounds and matches the original color).
2Step 2: Change the color of the current pixel.
3Step 3: Recursively call the helper function for the four adjacent pixels (up, down, left, right).

solution.py18 lines

1# Full working Python code
2
3def floodFill(image, sr, sc, color):
4    original_color = image[sr][sc]
5    if original_color == color:
6        return image
7
8    def dfs(r, c):
9        if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != original_color:
10            return
11        image[r][c] = color
12        dfs(r + 1, c)
13        dfs(r - 1, c)
14        dfs(r, c + 1)
15        dfs(r, c - 1)
16
17    dfs(sr, sc)
18    return image

ℹ

Complexity note: The time complexity is O(n) because each pixel is processed once. The space complexity is O(n) due to the recursion stack in the DFS approach.

1Understanding connected components is crucial for flood fill.
2Recursive approaches can simplify the logic of traversing adjacent pixels.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.