Algorithm Day92 - Unique Paths

Posted on In , Views:

🧩 Problem Description

A robot is located at the top-left corner of an 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).

How many possible unique paths are there?

💬 Examples

Example 1

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

Example 2

1
2
3
4
5
6
Input: m = 3, n = 2
Output: 3
Explanation:  
Right -> Down -> Down  
Down -> Down -> Right  
Down -> Right -> Down

💡 Intuition

At each cell (i, j), the number of unique paths to reach it is the sum of paths from the top (i-1, j) and from the left (i, j-1). This gives a dynamic programming relation.

Alternatively, this problem has a combinatorial solution using binomial coefficients: choosing (m-1) downs from (m+n-2) total moves.

🔢 Java Code (Dynamic Programming)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

🔢 Java Code (Combinatorics)

1
2
3
4
5
6
7
8
9
class Solution {
    public int uniquePaths(int m, int n) {
        long res = 1;
        for (int i = 1; i <= m - 1; i++) {
            res = res * (n - 1 + i) / i;
        }
        return (int) res;
    }
}

⏱ Complexity Analysis

  • DP approach:

    • Time: O(m × n)
    • Space: O(m × n) (can be optimized to O(n))

  • Combinatorics:

    • Time: O(m)
    • Space: O(1)

✍️ Summary

  • Grid path counting reduces to a classic DP problem.
  • Alternatively, solve with binomial coefficient.
  • Use combinatorics for very large grids to avoid DP overhead.

Related problems: lc-63 (Unique Paths II), lc-64 (Minimum Path Sum).