Paint Bucket Fill
EasyGraphsFree
Problem
You are building the paint-bucket tool of a pixel-art editor. The picture is image, a matrix of colour codes. The user clicks the pixel at (row, col) with the colour color.
The click recolours the clicked pixel and every pixel connected to it horizontally or vertically through pixels of the same original colour. Return the image after the fill.
Example 1
- Input:
- image = [[1,1,0],[1,0,0],[1,1,1]], row = 0, col = 0, color = 2
- Output:
- [[2,2,0],[2,0,0],[2,2,2]]
All the 1s are connected to (0,0) through other 1s, so they all become 2. The 0s are untouched.
Example 2
- Input:
- image = [[3,3],[3,3]], row = 0, col = 0, color = 3
- Output:
- [[3,3],[3,3]]
Filling with the colour already there changes nothing.
Constraints
- 1 ≤ rows, cols ≤ 100
- 0 ≤ image[r][c], color < 2^16
- 0 ≤ row < rows, 0 ≤ col < cols
Hint
Show the first hint
Which pixels change? Only those reachable from the click through pixels of the starting colour.
Walkthrough
How to approach it
01Clarify before coding
- Is connectivity 4-directional? Yes, diagonals do not spread the fill.
- Can I modify the input image and return it? Yes, returning the same matrix is fine.
- What if the new colour is the same as the old one? Nothing changes; return the image as is.
02Brute force
Repeatedly sweep the whole image, recolouring any pixel of the original colour that touches an already-recoloured pixel, until a sweep changes nothing.
Cost: Each sweep is O(r · c) and a winding region can need O(r · c) sweeps: O((r · c)²) in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.