Let's think of the grid in this problem as an undirected graph. For each node of the graph, we must check all its adjacent nodes to find a clear path. Can you recall a graph algorithm that can be used for checking adjacent nodes and shortest paths? One of our two favorite graph traversal algorithms fits this criterion, which is the Breadth First Search (BFS) algorithm.

Now, of course, the BFS algorithm needs to be modified so that it can be applied to the binary grid in the problem. The core approach for traversal is still the same, by adding and removing grid cells (instead of tree nodes) into the queue. To make our task easier, let's first consider some invalid cases.

• If we have a grid that has the top-left element as 1, then there will be no clear path (cannot start the path from 1).
• If a grid has the bottom-right element as 1, then there will be no clear path (cannot end the path).

Now let's get back to our main algorithm. To make the BFS work for a grid, we first define an array of all the possible directions that we can move in (up, down, diagonals), as unlike graphs grids are navigated by incrementing the x and y positions. We must also modify how we store elements in our plain old queue. Along with the value at each cell, the positions of cells are also stored. In this way, by incrementing the x and y values, we can move in the eight possible directions. As we traverse through these eight directions, we check for a couple of things,

• The value at the next cell (it should be 0, we do not want to go to cells with a value of 1)
• The x and y values of the next cell (they should not be out of bounds of the grid)

If the above conditions are met, the position and values of the next cell are successfully added to the queue. However, we would like to ensure that the current cell is not traversed again and that it does not show up while we check the eight possible directions for any other cell. To prevent such a case from occurring, the value at the current cell is changed from 0 to 1 to indicate that this position has already been visited. This process is repeated until we reach the bottom-right cell of the matrix.

One Pager Cheat Sheet

• Find the length of the shortest clear path in an n x n binary grid, or -1 if no clear path exists.
• We can use the Breadth First Search (BFS) algorithm to find a clear path between all adjacent nodes in the undirected graph.
• We can modify Breadth-First Search to find the shortest clear path in a binary grid, taking care to consider some invalid cases with the top-left and bottom-right elements.
• We are using a modified Breadth-First Search to traverse through a grid, storing values at each cell and adding/marking positions of each cell to/from our queue to ensure that we find the shortest clear path from the top-left cell to the bottom-right cell.
• By using a set to index and store the cells that have been visited, it is possible to ensure that no cell is visited twice as sets do not allow for duplicates of unique elements.
• The algorithm must traverse an m x n grid, resulting in O(m*n) time complexity.
• The time complexity of BFS is O(m×n) and of DFS is O(m+n) in a graph with m vertices and n edges.

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 shortestClearPath(grid) {

    let m = grid.length;

    let n = grid[0].length;

​

    if (grid[0][0] === 1 || grid[m - 1][n - 1] === 1) {

        return -1;

    }

​

    let directions = [

        [0, 1],

        [0, -1],

        [1, 0],

        [-1, 0],

        [1, 1],

        [1, -1],

        [-1, 1],

        [-1, -1]

    ];

​

    let queue = [

        [

            [0, 0], 1

        ]

    ];

    grid[0][0] = 1;

​

    while (queue.length > 0) {

        let [cellPosition, pathLength] = queue.shift();

        let x = cellPosition[0];

        let y = cellPosition[1];

You're doing a wonderful job. Keep going!

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