Repaint a region of an image
An image is a grid of integers, each a pixel colour. Given a starting pixel (sr, sc) and a
new color, repaint the starting pixel and every pixel connected to it that has the same original
colour. Two pixels are connected if they share a side (up, down, left or right), directly or through a chain of
such pixels. Return the image.
Examples
| Input | Output | Why |
|---|---|---|
image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 | [[2,2,2],[2,2,0],[2,0,1]] | The bottom-right 1 touches the region only diagonally, so it keeps its colour. |
image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 | [[0,0,0],[0,0,0]] | The new colour equals the old one: nothing changes. |
image = [[1,2,1],[2,1,2],[1,2,1]], sr = 1, sc = 1, color = 7 | [[1,2,1],[2,7,2],[1,2,1]] | The centre has no side neighbour of its colour. |
Constraints
- 1 ≤ rows, cols ≤ 50
- 0 ≤ image[r][c], color < 2¹⁶
- 0 ≤ sr < rows, 0 ≤ sc < cols
Hints
Hint 1
Record the original colour of (sr, sc) before changing anything.
Hint 2
A recursive fill(r, c) returns at once if the cell is outside the image or not the original colour; otherwise it repaints the cell and calls itself on the four neighbours.
Hint 3
If the new colour equals the original colour, return the image unchanged. Otherwise repainted cells still look unvisited and the recursion never ends.
Where people lose marks
- Not handling color equal to the original colour: infinite recursion.
- Reading image[r][c] before checking that (r, c) is inside the image.
- Treating diagonal pixels as connected.
- Comparing with the colour of the current pixel instead of the saved original colour, after the current one has already been repainted.
Dry run on [[1,1,1],[1,1,0],[1,0,1]],1,1,2
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7
Start at (1, 1): its original colour is 1. Repaint it 2.
-
Step 2 / 7
From (1, 1), (0, 1) has the original colour 1: repaint it 2 and try its neighbours.
-
Step 3 / 7
From (0, 1), (0, 2) has the original colour 1: repaint it 2 and try its neighbours.
-
Step 4 / 7
From (0, 1), (0, 0) has the original colour 1: repaint it 2 and try its neighbours.
-
Step 5 / 7
From (0, 0), (1, 0) has the original colour 1: repaint it 2 and try its neighbours.
-
Step 6 / 7
From (1, 0), (2, 0) has the original colour 1: repaint it 2 and try its neighbours.
-
Step 7 / 7
No repainted pixel has a neighbour of the original colour left. The corner pixel keeps its colour: it touches the region only diagonally.
How to think about it
The pixels of the starting colour form a graph in which each pixel is joined to the same-coloured pixels beside it, and the task is to visit the connected piece that contains the start. A depth-first flood fill does it with no separate visited set: once a pixel is repainted it no longer has the original colour, so the check that rejects other colours also rejects pixels already done.
That trick has one hole. If the new colour equals the old one, a repainted pixel still has the original colour, and the fill loops for ever. Returning early in that case closes it, and is also correct: nothing would change.
Complexity. Time O(rows · cols) · Space O(rows · cols) for the recursion in the worst case
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def flood_fill(image, sr, sc, color):
old = image[sr][sc]
if old == color:
return image # nothing to do, and filling would never stop
rows, cols = len(image), len(image[0])
def fill(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or image[r][c] != old:
return # outside, another colour, or already repainted
image[r][c] = color
fill(r - 1, c)
fill(r, c + 1)
fill(r + 1, c)
fill(r, c - 1)
fill(sr, sc)
return image#include <functional>
#include <vector>
std::vector<std::vector<int>> solve(std::vector<std::vector<int>> image, int sr, int sc, int color) {
const int old = image[sr][sc];
if (old == color) return image; // nothing to do, and filling would never stop
const int rows = image.size(), cols = image[0].size();
std::function<void(int, int)> fill = [&](int r, int c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] != old) return;
image[r][c] = color;
fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
};
fill(sr, sc);
return image;
}class Solution {
private int[][] image;
private int old, color;
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
this.image = image;
this.old = image[sr][sc];
this.color = color;
if (old != color) fill(sr, sc); // equal colours: nothing to do
return image;
}
private void fill(int r, int c) {
if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] != old) return;
image[r][c] = color;
fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
}
}function floodFill(image, sr, sc, color) {
const old = image[sr][sc];
if (old === color) return image; // nothing to do, and filling would never stop
const rows = image.length, cols = image[0].length;
const fill = (r, c) => {
if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] !== old) return;
image[r][c] = color;
fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
};
fill(sr, sc);
return image;
}fn solve<const N: usize>(image: &[[i64; N]], sr: i64, sc: i64, color: i64) -> Vec<Vec<i64>> {
let mut img: Vec<Vec<i64>> = image.iter().map(|row| row.to_vec()).collect();
let old = img[sr as usize][sc as usize];
if old == color {
return img; // nothing to do, and filling would never stop
}
fn fill(img: &mut Vec<Vec<i64>>, r: i64, c: i64, old: i64, color: i64) {
if r < 0 || c < 0 || r as usize >= img.len() || c as usize >= img[0].len() {
return;
}
if img[r as usize][c as usize] != old {
return;
}
img[r as usize][c as usize] = color;
fill(img, r - 1, c, old, color);
fill(img, r, c + 1, old, color);
fill(img, r + 1, c, old, color);
fill(img, r, c - 1, old, color);
}
fill(&mut img, sr, sc, old, color);
img
}import qualified Data.Map.Strict as M
solve :: [[Int]] -> Int -> Int -> Int -> [[Int]]
solve image sr sc color
| old == color = image -- nothing to do
| otherwise = [[M.findWithDefault 0 (r, c) final | c <- [0 .. cols - 1]] | r <- [0 .. rows - 1]]
where
rows = length image
cols = length (head image)
grid = M.fromList [((r, c), x) | (r, row) <- zip [0 ..] image, (c, x) <- zip [0 ..] row]
old = grid M.! (sr, sc)
final = fill grid (sr, sc)
-- the map is the image; a repainted cell no longer matches old, so it is never revisited
fill g (r, c) = case M.lookup (r, c) g of
Just x | x == old -> foldl fill (M.insert (r, c) color g) [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
_ -> gVariants to try
- Repaint only the border of the region (the pixels of the region that touch a pixel outside it).
- Return the number of distinct regions in the image, of any colour.
- Make it iterative with an explicit stack, for images of 10⁴ × 10⁴ pixels.
Next problems
Capture the enclosed regions
Turn every region of O cells that cannot reach the edge of the board into X. The trick is to search from the border inwards.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
Capture the enclosed regions
Turn every region of O cells that cannot reach the edge of the board into X. The trick is to search from the border inwards.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.