Unique Paths

Photo by Tara Scahill on Unsplash

There is a robot on a m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Taken from Leetcode.com

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

Constraints:

• 1 <= m, n <= 100

Approach

Let us consider 2 cases initially. What if :

• We have only one row: If we have only one row and n number of columns, there will be only one unique path.
• We have only one column: Same case as above, even if we have m number of rows, there will be only one unique path.
• For all other cases, we have 2 scenarios, we can move toward the right or the bottom. In short, we have 2 choices at any given point (i, j). Move (i+1, j) towards down, or move (i, j+1) towards the right.

This leads to the initial idea of recursion. We have the choices, make any choice, and calculate the unique paths.

Sample Recursion Tree for 2 x 3 matrix

From the recursion tree, we can see that there can be repeating sequences that we calculate again and this can be avoided by storing the result and reuse.

This gives us a hint to memorize the previous result and reuse it whenever we find the same pattern.

Code

Recursive Solution — Time Limit Exceeded

class Solution {
    public int uniquePaths(int m, int n) {
        return findUniquePaths(0, 0, m, n);
    }
    private int findUniquePaths(int currentRow, int currentCol, int row, int col) {
        if (currentRow == row - 1 && currentCol == col - 1) {
            return 1;
        }
        if (currentRow > row || currentCol > col) {
            return 0;
        }
        return findUniquePaths(currentRow + 1, currentCol, row, col) + findUniquePaths(currentRow, currentCol + 1, row, col);
    }
}

Recursive Solution With Memoization

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int [][] possibleRoutes = new int [m][n];
        for (int [] routes : possibleRoutes) {
            Arrays.fill(routes, -1);
        }
        return findUniquePaths(0, 0, m, n, possibleRoutes);
    }
    private int findUniquePaths(int currentRow, int currentCol, int row, int col, int [][] possibleRoutes) {
        if (currentRow == row - 1 && currentCol == col - 1) {
            return 1;
        }
        if (currentRow >= row || currentCol >= col) {
            return 0;
        }
        if (possibleRoutes[currentRow][currentCol] != -1) {
            return possibleRoutes[currentRow][currentCol];
        }
        int moveRight = findUniquePaths(currentRow, currentCol + 1, row, col, possibleRoutes);
        int moveDown = findUniquePaths(currentRow + 1, currentCol, row, col, possibleRoutes);
        return possibleRoutes[currentRow][currentCol] = moveRight + moveDown;
    }
}

Iterative Solution

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int [][] possibleRoutes = new int [m][n];
        // if we have only a single column, then there is only a single route
        for (int i = 0; i < m; i++) {
            possibleRoutes[i][0] = 1;
        }
        // if we have only a single row, then also there is only a single route
        for (int i = 0; i < n; i++) {
            possibleRoutes[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // to reach dp[i][j], we can use same paths thet we used to get to dp[i - 1][j]
                // dp[i][j - 1]
                possibleRoutes[i][j] += possibleRoutes[i - 1][j] + possibleRoutes[i][j - 1];
            }
        }
        return possibleRoutes[m - 1][n - 1];
    }
}

Time and Space Complexity

In recursive and iterative solutions, we traverse the matrix of size row x col. So the time complexity is O(row x col).

Extra space is used for storing the previous result. Space complexity is O(row * col)