Good afternoon! Here's our prompt for today.
Imagine the implementation for the paintbucket feature in Microsoft Paint, or how certain image filters work. You click on a specific pixel on a screen, and every similar-colored neighboring pixel would change to your selected color. Let's implement a simpler version of that feature.

You're given a n x n
matrix array of numbers. Let's say you'd like to replace all similar and connected cells of a certain number with another, starting at column 0
and row 0
.
So here's your input:
1const input = [
2 [1, 1, 1, 1, 1, 1, 1],
3 [1, 1, 1, 1, 1, 1, 0],
4 [1, 0, 0, 1, 1, 0, 1],
5 [1, 2, 1, 2, 1, 2, 0],
6 [1, 2, 1, 2, 2, 2, 0],
7 [1, 2, 2, 2, 1, 2, 0],
8 [1, 1, 1, 1, 1, 2, 1]
9]
And the final result of starting at column 0
and row 0
would be as follows:
1// floodFill(matrix, startingRow, startingCol, newValue)
2floodFill(input, 0, 0, 3);
3// [
4// [3, 3, 3, 3, 3, 3, 3],
5// [3, 3, 3, 3, 3, 3, 0],
6// [3, 0, 0, 3, 3, 0, 1],
7// [3, 2, 1, 2, 3, 2, 0],
8// [3, 2, 1, 2, 2, 2, 0],
9// [3, 2, 2, 2, 3, 2, 0],
10// [3, 3, 3, 3, 3, 2, 1]
11// ]
Notice how all the 1
s that were bordering the original 1
in column 0
and row 0
have been transformed to 3
.
Constraints
- Given matrix contains non negative integers
- The array is
0-indexed
- Let
|V|
,|E|
represent the number of vertices and edges of the graph (if you consider the matrix as a graph) - Expected time complexity :
O(|V|)
- Expected space complexity :
O(|V|)
considering the call stack
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
'PASSED: `floodFill([ [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1], [1, 2, 1, 2, 1, 2, 0], [1, 2, 1, 2, 2, 2, 0], [1, 2, 2, 2, 1, 2, 0], [1, 1, 1, 1, 1, 2, 1] ], 0, 0, 3)` should return `[[3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 0], [3, 0, 0, 3, 3, 0, 1], [3, 2, 1, 2, 3, 2, 0], [3, 2, 1, 2, 2, 2, 0], [3, 2, 2, 2, 3, 2, 0], [3, 3, 3, 3, 3, 2, 1] ]`;'
var assert = require('assert');
​
function floodFill(matrix, row, col, newVal) {
// Fill in this method
return matrix;
}
​
function replaceWithMatch(match, matrix, r, c, newVal) {}
​
const input = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 1, 1, 0, 1],
[1, 2, 1, 2, 1, 2, 0],
[1, 2, 1, 2, 2, 2, 0],
[1, 2, 2, 2, 1, 2, 0],
[1, 1, 1, 1, 1, 2, 1],
];
​
console.log(floodFill(input, 0, 0, 3));
​
class Graph {
constructor() {
this.adjacencyList = new Map();
this.verticesCount = 0;
}
​
addVertex(nodeVal) {
this.adjacencyList.set(nodeVal, []);
Here's how we would solve this problem...
How do I use this guide?
This problem is an implementation of the famous flood-fill algorithm. So we're given a matrix, and we need to traverse an element's neighbors, and then repeat. It's always beneficial to think through a smaller input first.
xxxxxxxxxx
const input = [
[1, 1, 1],
[1, 1, 1],
[1, 0, 0]
So starting at index [0][0]
(row 0
, column 0
), we're looking to move right, down, and bottom right (marked with *
s):
xxxxxxxxxx
const input = [
[1, *, 1],
[*, *, 1],
[1, 0, 0]
We don't need to worry about the other sides (above, left) because those nodes
don't exist.
What are we looking to do? We need to visit every neighbor, and then every one of its neighbors. This sounds like a graph
traversal problem.
How many times do we need to perform a node operation? As long as there are nodes that match the initial one that we clicked on or started at.
Knowing this, we could go with either go with a Breadth-first search
or a Depth-first search
approach.

What if we didn't want to use a queue
? We can use a recursive depth-first search
approach.
The idea here is to use some form of graph
traversal mechanism to ensure we cover all necessary vertices within the graph
that suit our conditions. Specifically, we are looking for vertices that match our origin point.
With that said, the pseudocode could be as simple as:
- Perform a
DFS
by attempting to visit a surrounding neighbor - See if the cell we're in meets this condition
- If yes, repeat step 1 for its neighbors
- If not, no-op and don't do anything
Complexity of Final Solution
Let |V|
, |E|
represent the number of vertices and edges of the graph, respectively. A DFS for a graph implemented as a 2d matrix has O(|V|)
time complexity, and O(|V|)
space complexity as in the worst case, we can have |V|
recursive calls being stored on the call-stack.
We are also giving the iterative solution using stack
in DFS below:
xxxxxxxxxx
def flood_fill(matrix, x, y, new_val):
# Check if the source is already in desired color
old_value = matrix[x][y]
if new_val == old_value:
return matrix
# Stack is used for iterative DFS
# Start from the source (x,y)
stack = [(x,y)]
​
# While the stack is not empty
while stack:
row, col = stack.pop()
# We move at 8 directions.
# So we make a list and make these 8 cells iteratively
for dirx in [-1, 0, 1]:
for diry in [-1, 0, 1]:
# Ignore dir=(0,0)
if dirx == 0 and diry == 0:
continue
cell = (row+diry, col+dirx)
# Check if the cells are within grid
if cell[0] >= 0 and cell[0] < len(matrix) and cell[1] >= 0 and cell[1] < len(matrix[0]):
# Check if cell is in old_value
if matrix[cell[0]][cell[1]] == old_value:
matrix[cell[0]][cell[1]] = new_val
stack.append(cell)
​
return matrix
One Pager Cheat Sheet
- Using the
flood-fill algorithm
, we need to think through a smaller input first to traverse an element's neighbors in the given matrix. - We are looking to traverse
row 0
,column 0
to theright
,down
andbottom right
(*). - We don't need to
traverse
thegraph
with either aBreadth-first search
orDepth-first search
approach as long as there are matchingnodes
for the initial one we started with. - We can replace the
queue
we usually use withDFS
using either a recursive approach withO(|V|)
time and space complexity, or an iterative approach using astack
for the same complexity.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
}
var assert = require('assert');
​
function floodFill(matrix, row, col, newVal) {
if (matrix[row][col] == newVal) {
return matrix;
}
replaceWithMatch(matrix[row][col], matrix, row, col, newVal);
return matrix;
}
​
function replaceWithMatch(match, matrix, r, c, newVal) {
if (matrix[r] && matrix[r][c] >= 0 && matrix[r][c] == match) {
matrix[r][c] = newVal;
if (matrix[r - 1]) {
// when there is no left neighbor
replaceWithMatch(match, matrix, r - 1, c, newVal);
}
replaceWithMatch(match, matrix, r, c - 1, newVal);
if (matrix[r + 1]) {
replaceWithMatch(match, matrix, r + 1, c, newVal);
}
replaceWithMatch(match, matrix, r, c + 1, newVal);
}
}
​
const input = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 1, 1, 0, 1],
[1, 2, 1, 2, 1, 2, 0],
[1, 2, 1, 2, 2, 2, 0],
[1, 2, 2, 2, 1, 2, 0],
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.