parikshan

flood-fill

Difficulty: Easy  ·  Topic: Graphs  ·  Practice it on parikshan: /practice/flood-fill/start

The story

A photo-editing intern opens Photoshop, clicks the magic-wand on a pixel, and the whole continuous region of the same colour gets recoloured. That is literally this algorithm. The same code recolours connected regions in MS Paint, Procreate, Affinity Designer, GIMP, Lightroom, and every CAD tool ever shipped. You will never write flood-fill for a real product without quietly thanking the person who taught you it.

This is the smallest possible BFS/DFS problem in the bank. Five minutes to learn, a lifetime of carrying the pattern. Every grid-traversal problem you ever solve is flood-fill plus an accumulator.

What's actually being asked

You are given an r × c grid where each cell holds a digit '0'..'9' (a colour). Starting from (sr, sc), recolour every cell reachable from the start by 4-neighbour moves through cells of the same original colour. Print the resulting grid.

If newColor equals the start cell's colour, the grid is unchanged.

The naive approach

There is no slower approach to flood fill. Every correct solution is O(r · c). The only thing that makes a naive solver slower than necessary is recursion: a 200x200 monochrome region of 40,000 cells exceeds Python's default recursion depth and crashes. Iterative BFS sidesteps that. The rest of the difficulty is in the special cases, not in the algorithm.

The key insight

Reachability under "same colour" is a graph traversal. Read the original colour before mutating anything. Walk neighbours, recolouring cells whose current colour equals the original colour and enqueuing them. Recolouring on enqueue doubles as the visited check: once a cell is recoloured, it no longer matches the original colour, so subsequent visits reject it.

The one trap that catches everyone exactly once: if newColor == originalColour, the recolouring is a no-op but neighbours still match the original colour, so they get enqueued forever. Special-case it: if the colours are equal, print the grid unchanged.

Step-by-step approach

  1. Read the grid, sr, sc, new_color.
  2. orig = grid[sr][sc].
  3. If orig == new_color: print the grid unchanged, return.
  4. Otherwise:
    • grid[sr][sc] = new_color.
    • Initialise dq = deque([(sr, sc)]).
    • While dq is non-empty:
      • Pop (x, y).
      • For each (dx, dy) in (1,0), (-1,0), (0,1), (0,-1):
        • nx, ny = x + dx, y + dy.
        • If 0 <= nx < r and 0 <= ny < c and grid[nx][ny] == orig:
          • grid[nx][ny] = new_color.
          • dq.append((nx, ny)).
  5. Print the resulting grid.

That is the algorithm. Every grid BFS you will ever write is this skeleton with one extra accumulator (count, sum, max, list) or one extra termination rule (depth limit, target cell, count limit).

Worked example

3 3
1 1 1
1 1 0
1 0 0
sr sc newColor = 1 1 2
  • orig = 1, new_color = 2, not equal.
  • Recolour (1,1) to 2. Deque = [(1,1)].
  • Pop (1,1). Neighbours: (0,1)=1 recolour and push, (2,1)=0 skip, (1,0)=1 recolour and push, (1,2)=0 skip.
  • Pop (0,1). Neighbours: (-1,1) out, (1,1)=2 already recoloured (no longer orig), (0,0)=1 recolour and push, (0,2)=1 recolour and push.
  • Pop (1,0). Neighbours: (0,0)=2 skip, (2,0)=1 recolour and push, (1,-1) out, (1,1)=2 skip.
  • Pop (0,0). All neighbours either out or no longer orig.
  • Continue draining the deque. All cells reachable from (1,1) through 1-coloured cells are now 2.

Output:

2 2 2
2 2 0
2 0 0

Complexity

  • Time: O(r · c). Each cell is enqueued at most once.
  • Space: O(r · c) worst case for the deque on a monochrome grid.

Common pitfalls

  • Not reading orig first: writing grid[sr][sc] = new_color before reading orig leaks the new colour into the comparator and you recolour cells that never matched.
  • Skipping the equal-colour short-circuit: when new_color == orig, the naive code never terminates because every neighbour still matches.
  • Recursive DFS on a 200x200 monochrome grid: blows Python's default 1000-depth limit. Iterative BFS is the safe choice; sys.setrecursionlimit(50000) is the safe choice if you insist on DFS.
  • Wrong neighbour set: 4-connectivity vs 8-connectivity is spec-defined. The article assumes 4. Read the spec.
  • Allocating a separate visited matrix: unnecessary; the recolour itself is the visited mark.

Where this shows up in the enterprise

  • Photoshop / GIMP / Procreate magic-wand selection: literal flood-fill on the pixel grid.
  • MS Paint paint-bucket tool: the canonical example.
  • CAD region-fill tools (AutoCAD, Fusion 360): flood-fill on the 2-D projection of a model.
  • Game maps (Unity, Unreal): runtime flood-fill identifies the player's currently reachable region of a procedurally generated level.
  • Industrial defect detection (Cognex, Keyence): flood-fill segments a single contiguous defect for measurement.
  • Medical imaging (Siemens Healthineers, GE Healthcare): flood-fill recolours a CT-scan slice for visualisation.
  • Cloudflare attack-traffic clustering: flood-fill on a (source, time) heatmap identifies a single botnet's footprint cells in one pass.
  • Satellite imagery (Maxar, Planet Labs): flood-fill segments a single flooded region, building, or field from a mask.
  • Spotify recommendations (analogy): flood-fill on the similarity graph from a seed track identifies the user's currently-listening cluster.

The pattern: a single seed, expand outward until the boundary changes. Every product with a "select all that look like this" gesture runs this code.

Variants you'll see elsewhere

  • number-of-islands: outer scan over all cells, one flood-fill per unvisited land cell, count the floods.
  • max-area-of-island: same outer scan, count cells inside the flood, take the max.
  • surrounded-regions: flood-fill from the border to mark "safe" cells, flip the rest.
  • island-perimeter: flood-fill, accumulate boundary edges instead of cells.
  • count-sub-islands: flood-fill on grid A, check each visited cell against grid B.
  • walls-and-gates / 01-matrix / rotting-oranges: multi-source flood-fill, propagate distance in the tuple.
  • pacific-atlantic-water-flow: two flood-fills from each ocean's border, intersect.

This problem is the seed pattern for every entry in the cluster. Master it and the rest are accumulator tweaks.

How parikshan turns this into a learning loop

Use this as the five-minute drill before any other graph problem:

  1. Practice mode, no AI, no hints. Write iterative BFS from scratch. Target: under five minutes from blank screen to AC.
  2. Exam mode, no AI. Same target.
  3. When you can write this cold in three minutes, the pattern is in your fingers. Every subsequent graph problem in the cluster will feel like an accumulator swap.

The exam mode integrity score on flood-fill is parikshan's smoke test: if you score below 80 on this, you have not internalised iterative BFS, and every harder problem in the cluster will be harder than it needs to be.

In the AI-integrated workspace

In production, agents write flood-fill correctly 95% of the time. The 5% failure mode is the equal-colour infinite loop: the agent's tests do not exercise the no-op case, the code ships, and a user with a particular workflow triggers a CPU-saturating loop in the renderer.

Your review takes ten seconds:

  1. Is orig read before the start cell is mutated?
  2. Is there an if orig == new_color: return (or equivalent) short-circuit at the top?
  3. Is the recolour on enqueue, not on pop?
  4. Is the traversal iterative or guarded against deep recursion?

Three "yes"es and one "iterative" and you can stamp approve. That is the entire skill. It costs ten seconds per review and prevents the production-CPU-loop bug that has been written into every paint tool's history at least once. parikshan is here to make those ten seconds automatic.