Leetcode 733. Flood Fill

Problem

You're building a digital painting application and need to implement the paint bucket tool. Given a 2D canvas represented as a grid of integers (where each integer represents a color), a starting pixel coordinate, and a target color, implement the fill operation.

The fill operation should change the color of the starting pixel and all pixels connected to it (horizontally or vertically) that share the same original color as the starting pixel. The operation spreads only through adjacent pixels in the four cardinal directions (up, down, left, right) — diagonal connections do not count.

Return the modified canvas after performing the fill operation.

Requirements

1. Change the starting pixel at position (sr, sc) to the new color
2. Recursively or iteratively change all adjacent pixels (up, down, left, right) that have the same original color
3. Do not change pixels that are separated by different colors
4. If the new color is the same as the starting pixel's original color, the canvas remains unchanged
5. Return the modified 2D grid

Constraints

• The canvas dimensions are m × n where 1 ≤ m, n ≤ 50
• Starting row sr is in range [0, m-1]
• Starting column sc is in range [0, n-1]
• Color values are integers in range [0, 65535]
• You must modify the input grid in place or return a new grid
• Expected time complexity: O(m × n)
• Expected space complexity: O(m × n) for the call stack in worst case

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 pixel at (1,1), we start with color 1. All connected pixels with color 1 are changed to 2. The resulting region forms a connected component in the top-left area of the canvas.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Output: [[0,0,0],[0,0,0]] Explanation: Since the starting pixel already has the target color, no changes occur.

Example 3:

Input: image = [[1,1,1],[1,2,1],[1,1,1]], sr = 1, sc = 1, color = 3 Output: [[1,1,1],[1,3,1],[1,1,1]] Explanation: Only the center pixel changes because its neighbors have a different color (1) than the starting pixel's color (2).

Hint 1: Graph Traversal This problem is essentially a connected component traversal. Think about how you would explore all cells that are reachable from the starting position while staying within cells of the same color. Both depth-first search (DFS) and breadth-first search (BFS) are viable approaches.

Hint 2: Early Termination Consider the edge case where the new color equals the original color of the starting pixel. What would happen if you didn't handle this specially? You could end up in an infinite loop or redundant work. Check this condition before starting your traversal.

Hint 3: Boundary Checking When exploring adjacent cells, ensure you check that coordinates are within the canvas bounds and that the adjacent cell has the original color before recursing or adding it to your queue.

Full Solution ` def paintFill(image, sr, sc, color): # Get the original color of the starting pixel original_color = image[sr][sc]

# If the new color is the same as original, no work needed
if original_color == color:
    return image

rows, cols = len(image), len(image[0])

def dfs(r, c):
    # Check bounds and color match
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if image[r][c] != original_color:
        return
    
    # Paint the current pixel
    image[r][c] = color
    
    # Recursively paint all four adjacent pixels
    dfs(r + 1, c)  # down
    dfs(r - 1, c)  # up
    dfs(r, c + 1)  # right
    dfs(r, c - 1)  # left

# Start the fill from the starting position
dfs(sr, sc)
return image

`

Approach:

The solution uses depth-first search (DFS) to traverse all connected pixels with the same original color. Here's how it works:

1. Early Exit Check: First, we store the original color and check if it matches the target color. If they're the same, we return immediately to avoid unnecessary work and potential infinite recursion.

2. DFS Traversal: Starting from the given position (sr, sc), we recursively explore all four cardinal directions (up, down, left, right).

3. Base Cases: For each recursive call, we check:

   • Is the position within bounds?
   • Does the current pixel have the original color?
   • If either check fails, we return without making changes.

4. Color Update: When we visit a valid pixel with the original color, we immediately change it to the new color. This serves two purposes: it performs the required color change and marks the pixel as visited (preventing infinite loops).

Alternative BFS Approach:

` from collections import deque

def paintFill(image, sr, sc, color): original_color = image[sr][sc] if original_color == color: return image

rows, cols = len(image), len(image[0])
queue = deque([(sr, sc)])
image[sr][sc] = color

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while queue:
    r, c = queue.popleft()
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
            image[nr][nc] = color
            queue.append((nr, nc))

return image

`

Complexity Analysis:

• Time Complexity: O(m × n) where m is the number of rows and n is the number of columns. In the worst case, we visit every pixel once when the entire canvas has the same color.
• Space Complexity: O(m × n) for the recursion call stack (DFS) or queue (BFS) in the worst case. This occurs when all pixels form one connected component, leading to maximum recursion depth or queue size.