Practice/Google/Leetcode 733. Flood Fill

Leetcode 733. Flood Fill

CodingMust

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