Find all unique paths in a grid

Given a grid where you can move either in down or right direction at any given point you have to find all the unique paths in it.

Example

Input:
m = 7, n = 3

Output:
28

A grid is represented by a two dimensional array and the user will always start at [0,0] and end at [m-1, n-1] as you can see in the image.

We are going to see two different solutions for this.
1. Based on dynamic programming (Iterative and Recursive)
2. Mathematical using combination and factorials.

Using dynamic programming to find the unique paths in a grid.

Conceptually this is how this works.

• We will start at [0,0] which is a unique path and end at [m-1, n-1].
• 1. If go down whats the unique paths?.
• 2. If go right whats the unique paths?.
• Total unique paths will be 1 plus 2.
• So every time we will call the same function twice with one in down direction and one in right direction and combine their results and return them.

Recursive

const uniquePathsRecursive = (m, n) => {
  //Initialize and empty grid with 1 as default value
  let dp = new Array(m+1).fill(1).map(x => new Array(n+1).fill(0));
  
    const recur = (r, c) => {
        //If we have reached to the exit then return 1 as unique path
        if (r == m && c == n) return 1;
        
        //If we are exceeding the grid walls then return 0
        if (r > m || c > n) return 0;
      
        //If value is already present then return it.
        if (dp[r][c]) return dp[r][c];
      
        //Else get all the unique paths by calling itself in down and right direction
        dp[r][c] = recur(r+1, c) + recur(r, c+1);
      
        //Return the result
        return dp[r][c];
    }
    
    //start from the beginning 
    return recur(1,1);
};

Input:
console.log(uniquePathsRecursive(7, 3));

Output:
28

Iterative

const uniquePathsIterative = (m, n) => {
    //Initialize and empty grid with 1 as default value
    let dp = new Array(m+1).fill(1).map(x => new Array(n+1).fill(0));
    
    //Itearte the grid
    for (let i=1;i<=m;i++) {
        for (let j=1;j<=n;j++) {
            //If unique path then update the data in dp cache
            if (i==1 && j==1) dp[i][j] = 1;
            
            //Else return the result of down and right unique paths
            else dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
  
    //Return the result from end
    return dp[m][n];
}

Input:
console.log(uniquePathsIterative(7, 3));

Output:
28

Time complexity in both the case is O(n ^ 2) because we are checking all the paths.
Space complexity is O(n ^ 2).

---

Mathematical approach using combinations and factorials to find the unique paths in a grid.

This approach works using binomial coefficient.

• We are going to make a total of m + n - 2 moves considering that we will start at [0,0] and end at [m-1, n-1].
• They will be split into m-1 right moves and n-1 down moves.
• Now we have to find how many ways are there to choose n-1 down moves out of m+n-2 moves and m-1 right moves out of m+n-2 moves.
• Then return the result.

const uniquePaths = (m, n) => {
    const total = m + n - 2;
    let k = n - 1;
    if (k === 0) return 1;
    let top = 1;
    let bottom = 1;
  
    for (let i = 0; i < k; i++) {
        top *= total - i;
        bottom *= i + 1;
    }

    return top / bottom;
};

Input:
console.log(uniquePaths(7, 3));

Output:
28

Time complexity: O(n).
Space complexity: O(1).