Skip to main content

16. Flood Fill

easyAsked at Roblox

Recolor a connected region starting from a source pixel — the same flood-fill primitive Roblox Studio uses to paint terrain biomes and propagate block-color changes across adjacent voxels.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an image represented by an m x n integer grid, a starting pixel (sr, sc), and a new color. Perform a flood fill: starting from (sr, sc), change the color of all connected pixels that share the same original color to the new color. Connected means directly adjacent (up, down, left, right). Return the modified image.

Constraints

  • m == image.length, n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], color <= 65535

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: The center pixel and all connected 1-valued pixels become 2.

Example 2

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

Explanation: New color equals original — no change needed.

Approaches

1. Brute force — recursive DFS without early exit

Recursively visit every neighbor, changing color even when the new color equals the original, which risks infinite recursion.

Time
O(m*n)
Space
O(m*n) call stack
function floodFill(image, sr, sc, color) {
  const orig = image[sr][sc];
  const rows = image.length, cols = image[0].length;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (image[r][c] !== orig) return;
    image[r][c] = color;
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }

  if (orig !== color) dfs(sr, sc);
  return image;
}

Tradeoff:

2. Optimal — iterative BFS

Use a queue to avoid call-stack depth issues on large grids, processing each cell once with an early-exit guard when old color equals new color.

Time
O(m*n)
Space
O(m*n) queue
function floodFill(image, sr, sc, color) {
  const orig = image[sr][sc];
  if (orig === color) return image;
  const rows = image.length, cols = image[0].length;
  const queue = [[sr, sc]];
  image[sr][sc] = color;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  while (queue.length) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === orig) {
        image[nr][nc] = color;
        queue.push([nr, nc]);
      }
    }
  }
  return image;
}

Tradeoff:

Roblox-specific tips

Roblox interviewers often extend this problem to 3D voxel grids or ask you to track which cells changed for network-delta sync. Mention the early-exit guard (orig === color) — it shows awareness of edge cases that matter when this runs thousands of times per second in a live game engine.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Flood Fill and other Roblox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →