Unique Paths

Share

A robot is located at the top-left corner of an m x n grid. 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. How many possible unique paths are there?

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 3 unique paths: Right→Down→Down, Down→Right→Down, Down→Down→Right.

Solution Approach - DP Grid

We build a 2D DP table where dp[i][j] represents the number of unique paths to reach cell (i, j). Since the robot can only move right or down, each cell can be reached from the cell above or the cell to the left.

  • Initialize the first row and first column with 1 since there is exactly one way to reach any cell in the first row (keep going right) or first column (keep going down).
  • For all other cells: dp[i][j] = dp[i-1][j] + dp[i][j-1].
  • Return dp[m-1][n-1] as the answer.
Java
public class UniquePaths {

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // First row and first column all have 1 unique path
        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];
    }
}
Complexity Analysis:

Time complexity: O(m * n) to fill the entire grid.
Space complexity: O(m * n) for the DP table; can be optimized to O(n) using a single row array.