Unique Paths

Description

Unique Paths
There is a robot on an 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:

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:

Right -> Down -> Down
Down -> Down -> Right
Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Recursion

The idea is the end goal would be 1 then we keep adding to right and bottom ad we are using DFS and anything out of bounds would be 0
Intuition: From any cell $(r, c)$ , the number of paths to the destination equals the sum of paths by moving Down $(r + 1, c)$ plus paths by moving Right $(r, c + 1)$ .
Time Complexity: $O (2^{m + n})$
Space Complexity: $O (m + n)$ (call stack recursion depth)

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(0,0,m,n);
    }
 
    int dfs(int i, int j, int m, int n) {
        if ((i == m - 1) && (j == n - 1))
            return 1;
 
        if (i >= m || j >= n)
            return 0;
 
        return dfs(i+1,j,m,n) + dfs(i,j+1,m,n);
    }
}

1D DP - Backward

Time & Space Complexity
Time complexity: $O (m * n)$
Space complexity: $O (n)$

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,1);
 
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[j] += dp[j+1];
            }
        }
 
        return dp[0];
    }
}

1D DP - Forward

Intuition: Computing cell $(i, j)$ only requires values from the previous row (dp[j]) and the current row’s left cell (dp[j-1]). Instead of storing the full $m \times n$ matrix, you can compress it into a single 1D array of size $n$ and update it row by row.

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1); // Represents the first row (all 1s)
 
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1]; // dp[j] (from top) + dp[j-1] (from left)
            }
        }
 
        return dp[n - 1];
    }
}

Time Complexity: $O (m \times n)$
Space Complexity: $O (n)$

Combinatorics / Math

Intuition: No matter which route is taken, the total number of moves will always be $N = (m - 1) + (n - 1)$ . Out of these $N$ total steps, you simply choose $(m - 1)$ of them to be Down moves. This is the combinations problem:
$(k N) = (m - 1 m + n - 2)$

class Solution {
    public int uniquePaths(int m, int n) {
        int N = m + n - 2;
        int r = Math.min(m - 1, n - 1); // Pick smaller r to minimize loop iterations
        long ans = 1;
 
        for (int i = 1; i <= r; i++) {
            ans = ans * (N - r + i) / i;
        }
 
        return (int) ans;
    }
}

Time Complexity: $O (min (m, n))$
Space Complexity: $O (1)$

Obsidian Notes

Explorer