A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
var uniquePaths = function(m, n) {
//can't go backwards, so it's always forward
let matrix=[];
let cache=[];
//create edges
for (let i=0;i<n;i++) { //for every row
if (!matrix[i]) {
matrix[i]=[];
}
matrix[i][m-1]=1;
}
for (let i=0;i<m;i++) { //for every column
matrix[n-1][i]=1;
}
//console.log(matrix);
//go through and sum up from bottom left corner
for (let i=n-2;i>=0;i--) { //offset by 2 since edges already made
for (let j=m-2;j>=0;j--) {
//sum up right and bottom
//console.log(i,j);
matrix[i][j]=matrix[i+1][j]+matrix[i][j+1];
}
}
//console.log(matrix);
return matrix[0][0];
};Approaches
When I first looked at this problem, my first thought is how to draw this in my mind. We want a generic algorithm, but sometimes it’s good to draw out a few examples in your head first. The samples give a good intuition of what may work or may not work.
Matrix Representation as 2D Array
In terms of representation, we can see the box as a 2-dimensional matrix. You can interchange the rows and columns as long as you keep track of each. For ease of use here, we represent rows as n and columns as m. Here we represent n/rows as the first dimension of the array and m/columns as the second dimension of the array.
Examples
Let’s look at a few examples. We start off with a 2×2 matrix. The answer is 2 ways, because you can go down->right or right->down.
What about a 3×3 matrix? Or a 4×4 matrix? For the 3×3, think of the bottom 3×3 of the below table (we used one table for simplicity and to avoid repeats).
| 20 | 10 | 4 | 1 |
| 10 | 6 | 3 | 1 |
| 4 | 3 | 2 | 1 |
| 1 | 1 | 1 | 1 |
Notice that at the bottom there’s only one path to get to the destination… going right all the way to the end. There’s also only one path to go to the destination from right most edge, which is going down all the way to the end. This accounts for the 1s along the bottom and right edge.
Now let’s build it up from that base. At each cell, the number of unique paths is the sum of the bottom and right cell. Why is that? You can move right and the # of unique paths is the right cell. You can move down and the # of unique paths is the bottom cell. Thus the total # of unique paths at that cell is the sum of the bottom cell and the right cell. In terms of algorithm we can build that up from there.
Code Breakdown
Now let’s go over the code section by section.
//create edges
for (let i=0;i<n;i++) { //for every row
if (!matrix[i]) {
matrix[i]=[];
}
matrix[i][m-1]=1;
}
for (let i=0;i<m;i++) { //for every column
matrix[n-1][i]=1;
}
First we create the edges of 1s described above. Note that we can’t access the 2nd dimension of the 2D matrix without the first dimension being initialized (can’t access index of undefined). So on our row iteration, if it doesn’t exist, we initialize the first dimension at that index to an empty array.
//go through and sum up from bottom left corner
for (let i=n-2;i>=0;i--) { //offset by 2 since edges already made
for (let j=m-2;j>=0;j--) {
//sum up right and bottom
//console.log(i,j);
matrix[i][j]=matrix[i+1][j]+matrix[i][j+1];
}
}
Now we create the matrix. We’ve already initialized the bottom and right edges, so in our for loops we offset by 2. Half of that offset is to keep in mind that array indexes start at 0 and go to n-1 for n elements. The second half of that offset is because the edge was already made. We don’t want to repeat, and note that our matrix element operation references bottom and to the right, so we don’t want to go out of bounds.
The completed matrix now consists of a table like the one we have above. Therefore the solution is the top left corner of the matrix, or matrix[0][0].
Hope you enjoyed this tutorial, and check back often for more programming advice.