# Unique Paths

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 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;
};``````

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).

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