Mark As Completed Discussion

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.

Description

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:

JAVASCRIPT
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:

JAVASCRIPT
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?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's how we would solve this problem...

How do I use this guide?