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 1s 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 our guided, illustrated walk-through.

How do I use this guide?