Unique Paths

MediumDynamic ProgrammingMathCombinatorics
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebookMicrosoftBloomberg

Approach

Unique Paths

Problem Statement

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.

Examples

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 -> Right -> Down
3. Down -> Down -> Right

Constraints

  • 1 ≤ m, n ≤ 100

Approach

Key Insight

To reach cell (i, j), must come from (i-1, j) or (i, j-1)!

Therefore: dp[i][j] = dp[i-1][j] + dp[i][j-1]

This is a classic 2D DP problem.

Solution 1: 2D Dynamic Programming

Build DP table bottom-up.

Algorithm:

  1. Create m×n DP table
  2. Initialize first row and column to 1 (only one way to reach)
  3. For each cell (i, j):
    • dp[i][j] = dp[i-1][j] + dp[i][j-1]
  4. Return dp[m-1][n-1]

Solution 2: Space-Optimized DP

Only need previous row.

Algorithm:

  1. Use 1D array of size n
  2. For each row:
    • Update current row based on previous
    • Current cell = left + top
  3. Return last element

Solution 3: Math (Combinatorics)

This is actually a combinatorics problem!

Algorithm:

To reach (m-1, n-1) from (0, 0):

  • Need (m-1) down moves
  • Need (n-1) right moves
  • Total moves = (m-1) + (n-1) = m+n-2
  • Answer = C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)

Complexity Analysis

2D DP:

  • Time Complexity: O(m × n) - fill entire table
  • Space Complexity: O(m × n) - DP table

1D DP:

  • Time Complexity: O(m × n) - same computation
  • Space Complexity: O(n) - single row

Math Solution:

  • Time Complexity: O(m + n) - calculate combination
  • Space Complexity: O(1) - only variables

Pattern Recognition

This problem demonstrates:

  • 2D Dynamic Programming pattern
  • Grid traversal counting
  • Space optimization technique
  • Mathematical approach alternative
  • Foundation for Unique Paths II (with obstacles)

Solution

java
1class Solution {
2    // Solution 1: 2D Dynamic Programming
3    public int uniquePaths(int m, int n) {
4        // Create DP table
5        int[][] dp = new int[m][n];
6
7        // Initialize first row and column
8        for (int i = 0; i < m; i++) {
9            dp[i][0] = 1;
10        }
11        for (int j = 0; j < n; j++) {
12            dp[0][j] = 1;
13        }
14
15        // Fill DP table
16        for (int i = 1; i < m; i++) {
17            for (int j = 1; j < n; j++) {
18                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
19            }
20        }
21
22        return dp[m - 1][n - 1];
23    }
24
25    // Solution 2: Space-Optimized DP (1D array)
26    public int uniquePathsOptimized(int m, int n) {
27        // Only need current row
28        int[] dp = new int[n];
29
30        // Initialize first row
31        for (int j = 0; j < n; j++) {
32            dp[j] = 1;
33        }
34
35        // Update row by row
36        for (int i = 1; i < m; i++) {
37            for (int j = 1; j < n; j++) {
38                // Current cell = left + top
39                dp[j] = dp[j] + dp[j - 1];
40            }
41        }
42
43        return dp[n - 1];
44    }
45
46    // Solution 3: Math (Combinatorics)
47    public int uniquePathsMath(int m, int n) {
48        // Need (m-1) downs and (n-1) rights
49        // Total moves = m + n - 2
50        // Answer = C(m+n-2, m-1)
51
52        if (m == 1 || n == 1) {
53            return 1;
54        }
55
56        // Make m-1 <= n-1 for efficiency
57        if (m > n) {
58            int temp = m;
59            m = n;
60            n = temp;
61        }
62
63        long result = 1;
64        int j = 1;
65
66        // Calculate C(m+n-2, m-1)
67        for (int i = n; i < m + n - 1; i++) {
68            result *= i;
69            result /= j;
70            j++;
71        }
72
73        return (int) result;
74    }
75
76    // Solution 4: Cleaner DP
77    public int uniquePathsClean(int m, int n) {
78        int[][] grid = new int[m][n];
79
80        for (int i = 0; i < m; i++) {
81            for (int j = 0; j < n; j++) {
82                if (i == 0 || j == 0) {
83                    grid[i][j] = 1;
84                } else {
85                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
86                }
87            }
88        }
89
90        return grid[m - 1][n - 1];
91    }
92}
93
Loading visualizer...