Flood Fill
Easy About 10 min Free, no account needed
The paint-bucket tool - including the click that changes nothing.
The brief
image is a grid of colors, where image[r][c] is the pixel at row r, column
c. Starting from the pixel at row sr, column sc, recolor every pixel that
has the start pixel's original color and connects to it through up, down, left
or right steps (not diagonals). Return the recolored grid.
FloodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2) returns [[2,2,2],[2,2,0],[2,0,1]].
The bottom-right 1 keeps its color because it only touches the region
diagonally.
The grid has 1 to 200 rows and 1 to 200 columns, and (sr, sc) is always inside
it. Do not mutate image; return a new grid.
When the new color equals the region's current color, there is nothing to do, but a fill that re-visits already-painted pixels recurses forever on exactly that case. The hidden test clicks a region with its own color.
Starter code
using System;
public class Solution
{
// TODO: return the image with the 4-connected region around (sr, sc) recolored.
public int[][] FloodFill(int[][] image, int sr, int sc, int color)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Depth-first search
- Recurse or use an explicit stack to explore connected regions, paths and components.
Related katas
- Number of Islands Medium Free Count the connected patches of land in a grid.
- Longest Cycle in a Functional Graph Hard Free Find the largest directed cycle without retracing every path.
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.