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 the right, down and bottom right (*).
• We don't need to traverse the graph with either a Breadth-first search or Depth-first search approach as long as there are matching nodes for the initial one we started with.
• We can replace the queue we usually use with DFS using either a recursive approach with O(|V|) time and space complexity, or an iterative approach using a stack 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],

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.