Finding the Shortest Path in a Matrix

A question that I've seen come up in interviews a few times goes something like this:

Given a square matrix, what's the shortest distance to get from point A to point B?

This problem varies, both in terms of what points A and B are, and what directions you're allowed to travel in. One common variation is that you have a matrix filled with 0's and 1's, and you have to go from the top left corner to the bottom right corner. You can only move up, left, right, and down on the 1's. An example input would be:

[[1, 0, 1],
[1, 1, 1],
[0, 1, 1]]

Just by looking at this, you can see that the shortest path would be 4 moves long (and there's a few ways that path can be drawn). However, solving it with code is another issue.

Breadth First Search

This is an example of breadth first search. Breadth first search (BFS) enables you to find the shortest distance between two points. BFS means you visit each child node, and then each of those child nodes, until you find your target.

This blog post is going to be the first in a series about how to approach this kinds of problems using JavaScript. I find this problem to be tricky, as it relies on having a pretty good grasp of graph theory and dynamic programming, so I thought it could be broken down into sections.

In this first post, I'm going to look at how to do a simple breadth first search using JavaScript.

BFS and Binary Trees

To start, breadth first searches use queues, which means the first item you add to the queue is the first item you remove from the queue. To add to the queue is to "enqueue" and to remove from the queue is to "dequeue".

Breadth first searches are often explained using binary trees. Here's an example of a binary tree.

Tree image

If you were to do a breadth first search on this, this is the path you would take:

The order of nodes you'd check would be 6, 4, 8, 3, 5, 7, 9. In a BFS, you start with one node, check each of its children, then check of those children's children. 6 would be the first element added to the queue, and also the first one removed and checked.

Lets say you were given this tree, but it were already represented as an object. It may look something like this:

const tree = [
  {value: 6, left: 4, right: 8},
  {value: 4, left: 3, right: 5},
  {value: 8, left: 7, right: 9},
  {value: 3, left: null, right: null},
  {value: 5, left: null, right: null},
  {value: 7, left: null, right: null},
  {value: 9, left: null, right: null}
]

Lets say you were asked to see if the value 5 were in this tree. You could do that with a breadth first search. The first thing you'd do is set up a queue, which would keep track of which nodes you were about to search. Then, you'd want to put the first node in the queue.

function BFS(tree, target) {
  let queue = []
  queue.push(tree[0])

  //...
}

Then, you need to create a while loop. As long as there are nodes left to check--as in, as long as there are still things in the queue--keep checking them.

function BFS(tree, target) {
  let queue = []
  queue.push(tree[0])

  while (queue.length > 0) {
    //...
  }
}

Then, you want to dequeue the first node from the queue and check it. Because queues are first in first out, we do that with the shift() method. Right away, you can check if the value of the current node is the target value. If it is, the node is in the tree, and you can return true.

function BFS(tree, target) {
  let queue = []
  queue.push(tree[0])

  while (queue.length > 0) {
    let current = queue.shift()

    if (current.value === target) {
      return true
    }
    //...
  }
}

If the current node is not the target, then we have to add the node's left and right children to the queue, so that they can be checked.

function BFS(tree, target) {
  let queue = []
  queue.push(tree[0])

  while (queue.length > 0) {
    let current = queue.shift()

    if (current.value === target) {
      return true
    }
    if (current.left) {
      queue.push(tree[current.left])
    }
    if (current.right) {
      queue.push(tree[current.right])
    }
  }
  //...
}

If the target is not in the tree, then 'false' should be returned. This gives us the entirety of searching a binary tree using breadth first search:

function BFS(tree, target) {
  let queue = []
  queue.push(tree[0])

  while (queue.length > 0) {
    let current = queue.shift()

    if (current.value === target) {
      return true
    }
    if (current.left) {
      queue.push(tree[current.left])
    }
    if (current.right) {
      queue.push(tree[current.right])
    }
  }
  return false
}

Now that we've figured out whether or not a target is in a tree, how would we find out the distance between the root and the target? I'll explore finding a path's distance in the next blog post.