Flood Fill Paintbucket (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Instacart, Twitter, Palantir, Zillow, Snap, Workday, Intercom, Goldman Sachs, Red Hat, Walmart Labs, Gusto, Blend, Illumio, Digitate, Pagerduty, Cornerstone, Elastic, and Sailpoint.

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