Coding Interview PatternsUnique Paths
MediumDynamic Programming

Unique Paths

Explanation & Solution

Practice Problem

Description

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 can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner (i.e., grid[m-1][n-1]).

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Input: m = 3, n = 7

Output: 28

Explanation: From the top-left corner, there are 28 unique paths to reach the bottom-right corner.

Constraints

  • 1 <= m, n <= 100

Approach

Dynamic Programming pattern

1. Understand the Grid Movement

  • The robot starts at the top-left corner (0, 0) and must reach (m-1, n-1)
  • At each step, the robot can only move right or down
  • The number of unique paths to any cell equals the sum of paths from the cell above and the cell to the left

2. Initialize the DP Array

  • Create a 1D array dp of size n, filled with 1
  • The first row is all 1s because there is only one way to reach any cell in the top row (move right repeatedly)

3. Fill Row by Row

  • For each row i from 1 to m - 1, iterate across columns j from 1 to n - 1
  • The first column stays 1 because there is only one way to reach any cell in the leftmost column (move down repeatedly)

4. Apply the Recurrence

  • dp[j] += dp[j - 1] means: paths to cell (i, j) = paths from above (dp[j], the old value from the previous row) + paths from the left (dp[j - 1], already updated for the current row)
  • This works because we process left to right, so dp[j - 1] reflects the current row while dp[j] still holds the previous row's value

5. Return the Result

  • After processing all rows, dp[n - 1] contains the number of unique paths to the bottom-right corner

Key Insight

  • This is a classic grid DP problem where each cell depends on its top and left neighbors
  • The 1D DP optimization reduces space from O(m * n) to O(n) by reusing a single row
  • Time complexity is **O(m * n)** for filling the entire grid

Solution Code

Previous
Decode Ways
Next
Minimum Path Sum