💬 Discord
Sign In
NeetCode #559LC-733EasyGraphs
← Back to All Problems

#559 · #733 · Flood Fill(图像渲染)

📌 Problem Statement & Constraints

You are given an image as an m x n integer grid, a starting pixel (sr, sc) and a new color. Perform a flood fill: recolor the starting pixel and all 4-directionally connected pixels of the same original colour. Return the modified image. Constraints: 1 <= m, n <= 50, 0 <= color <= 65535.

💡 Core Algorithmic Approaches

  1. Record the original colour, then DFS from the start, recolouring matching pixels.
  2. The recursion must compare against the original colour, not the new one.
  3. Guard against original == color: otherwise the DFS would recurse forever, since every recoloured cell would still match.
  4. This is the canonical flood-fill template.

💻 Benchmark Python3 Implementation

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                   # nothing to do (also prevents infinite recursion)
        m, n = len(image), len(image[0])

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < m and 0 <= 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 Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited at most once.
💾 Space Complexity
O(m * n) for the recursion stack in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the original == color guard: the DFS would never terminate.
  • Comparing against the new colour: after recolouring, the check would fail immediately.
  • Forgetting the bounds check before indexing: it must come first.
  • Using 8-directional connectivity: only the four cardinal directions count.