LeetCode - Unique Paths

Problem statement

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?

Problem statement taken from: https://leetcode.com/problems/unique-paths

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

Constraints:

- 1 <= m, n <= 100
- It's guaranteed that the answer will be less than or equal to 2 * 10^9

Explanation

Brute force approach

As per the problem statement the robot can move either down or right. We can use recursion to find the count. Let numberOfPaths(m, n) represent the counts of path to reach row number m and column number n in the grid. numberOfPaths(m, n) in C++ can be recursively written as following.

int numberOfPaths(int m, int n){
    if (m == 1 || n == 1)
        return 1;

    return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
}

The time complexity of the above solution is exponential. There are many overlapping sub-problems and hence we can use dynamic programming approach to avoid re-computing overlapping sub-problems.

Dynamic programming approach

We can avoid re-computing the overlapping sub-problems by constructing a temporary 2D array count[][] in bottom up manner using the above recursive approach.

int numberOfPaths(int m, int n){
    // create a 2D array to store results of sub-problems
    int count[m][n];

    // count of paths to reach any cell in first column is 1
    for (int i = 0; i < m; i++)
        count[i][0] = 1;

    // count of paths to reach any cell in first row is 1
    for (int j = 0; j < n; j++)
        count[0][j] = 1;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++)
            count[i][j] = count[i - 1][j] + count[i][j - 1];
    }

    return count[m - 1][n - 1];
}

The time complexity of the above program is O(mn). The space complexity is O(mn). We can reduce the space more by O(n) where n is column size.

int numberOfPaths(int m, int n){
    int count[n] = { 1 };
    count[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
            count[j] += count[j - 1];
        }
    }

    return count[n - 1];
}

Combinatorics approach

We have to calculate m+n-2 C n-1 here which will be (m+n-2)! / (n-1)! (m-1)!

Let's check the algorithm on how to compute the above formula:

- set paths = 1

- loop for i = n; i < m + n - 1; i++
  - set paths = paths * i
  - update paths = paths / (i - n + 1)

- return paths

C++ solution

class Solution {
public:
    int uniquePaths(int m, int n) {
        long int paths = 1;

        for(int i = n; i < m + n - 1; i++){
            paths *= i;
            paths /= (i - n + 1);
        }

        return int(paths);
    }
};

Golang solution

func uniquePaths(m int, n int) int {
    paths := 1

    for i := n; i < m + n - 1; i++{
        paths *= i
        paths /= (i - n + 1)
    }

    return paths
}

Javascript solution

var uniquePaths = function(m, n) {
    let paths = 1;

    for(let i = n; i < m + n - 1; i++){
        paths *= i;
        paths /= (i - n + 1);
    }

    return paths;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: m = 3, n = 7

Step 1: set paths = 1

Step 2: loop for i = n; i < m + n - 1
         i = 7
         7 < 7 + 3 - 1
         7 < 9
         7 < 9
         true

         paths = paths * i
         paths = 1 * 7
               = 7

         paths = paths / (i - n + 1)
               = 7 / (7 - 7 + 1)
               = 7 / 1
               = 7

         i++
         i = 8

Step 3: loop for i < m + n - 1
        8 < 8 + 3 - 1
        8 < 9
        8 < 9
        true

        paths = paths * i
        paths = 7 * 8
              = 56

        paths = paths / (i - n + 1)
              = 56 / (8 - 7 + 1)
              = 56 / 2
              = 28

        i++
        i = 9

Step 4: loop for i < m + n - 1
        9 < 8 + 3 - 1
        9 < 9
        false

Step 5: return paths

So we return answer as 28.