Code Logo

Unique Paths

Published at24 Jul 2026
Created by
Medium 0 views
Like0

A robot is located at the top-left corner of an m x n grid. It can only move either right or down at each step. The robot wants to reach the bottom-right corner. How many possible unique paths are there?

This is a classic 2D DP problem. The number of ways to reach cell (i,j) is the sum of ways from above (i-1,j) and from the left (i,j-1): dp[i][j] = dp[i-1][j] + dp[i][j-1]. The base case is dp[0][j] = 1 (only right moves) and dp[i][0] = 1 (only down moves).

The space can be optimized to O(n) by using a single row array that updates left to right: dp[j] += dp[j-1]. This works because dp[j] (above) still holds the value from the previous row before update.

Edge cases include m=1 or n=1 (return 1, only one path along a straight line), and large grids where the result may exceed 32-bit integers.

The combinatorial formula for unique paths is C(m+n-2, m-1) which counts choosing m-1 down moves among m+n-2 total moves. The DP approach is equivalent but builds the solution iteratively, which is easier to understand and extend to problems with obstacles.

The space-optimized version uses a single array where dp[j] is updated left-to-right each row. This works because dp[j] before update represents the value from the row above (dp[i-1][j]), and dp[j-1] after update represents the value from the current row (dp[i][j-1]).

Example Input & Output

Example 1
Input
1, 5
Output
1
Explanation

1x5: only one path right.

Example 2
Input
3, 7
Output
28
Explanation

3x7 grid has 28 unique paths.

Example 3
Input
3, 3
Output
6
Explanation

3x3 grid has 6 paths.

Example 4
Input
5, 1
Output
1
Explanation

5x1: only one path down.

Example 5
Input
3, 2
Output
3
Explanation

3x2 grid has 3 paths.

Algorithm Flow

Recommendation Algorithm Flow for Unique Paths
Recommendation Algorithm Flow for Unique Paths

Solution Approach

DP: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Space-optimized to O(n): dp[j] += dp[j-1] for each row.

function solution(m, n) {
  var dp = new Array(n).fill(1);
  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
}

Time O(m*n), Space O(n).

Best Answers

java
class Solution {
    public int solution(int m, int n) {
        int[] dp=new int[n];
        for (int j=0;j<n;j++) dp[j]=1;
        for (int i=1;i<m;i++) {
            for (int j=1;j<n;j++) {
                dp[j]+=dp[j-1];
            }
        }
        return dp[n-1];
    }
}