Unique Paths

Leetcode #62 — a JavaScript Solution

This puzzle requires you to calculate the total number of unique paths from the top lefthand corner of a grid to the bottom righthand corner. You can only travel to the right or down, but may switch directions as much as you want.

Here’s one possible path for a 3 x 4 grid:

The grid above is has 10 possible solutions, and is simple enough that you can, with not too much trouble, imagine all 10 paths visually. However, as the grid expands, the permutations become much more difficult to keep track of.
A 5 x 5 grid has 70 possibilities!

Furthermore, mapping each of the possibilities to try to find doesn’t help. There is no good pattern evident for the sequence of paths.

The Solution

Aha moment! Instead of trying to keep track of the paths, we just need to determine how many different ways each square can be approached from and then add these totals for the next square of the grid.

Because we are moving from left to right and top to bottom, each of the edge squares ( the top row and the left hand column) need to be set to 1 (there is only one way to approach each of these squares.

The squares diagonally (down and to the right) are calculated by adding the left and upper adjacent squares until we reach the final square with the total number of possibilities!

In JavaScript we can accomplish this using a two dimensional array :[rows[columns]] to keep track of and reference the previous sums.

We create an array and initialize it with an inner array empty array which will contain the first row.

Next we fill the length of the first row with 1’s (our initial values).

Finally we iterate through the rest of the rows, adding an initial value of 1 for the first element (our left hand edge value), and then filling the next square with the sum of the value to the left and the value above until we reach the end, returning the last value of the array, our solution.

function numPaths(m, n) {
  const result = [[]];
  // Adding the first row of ’1’s to the array
  for (let i = 0; i < n; i += 1) {
    result[0].push(1);
  }
  // iterating over each of the rows
  for (let i = 1; i < m; i += 1) { 
    result.push([1]);    // adding 1 to the first, left most square
    
      // Getting the total for the current square
    for (let j = 1; j < n; j += 1) {
      result[i][j] = result[i][j - 1] + result[i - 1][j];
    }
  }
// Return the bottom right hand value that has the total.
  return result[m - 1][n - 1];
}

That’s it!