Good morning! 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?