{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Unique Paths – Solution & Complexity

Interview solutions
/
Unique Paths

1. Understand the Pattern

  • The robot only moves right or down, so every path is a sequence of moves.
  • Reaching cell (i, j) is only possible from (i-1, j) (a down move) or (i, j-1) (a right move).
  • The number of ways to reach a cell is the sum of the ways to reach those two neighbours.

2. Dynamic Programming Table

  • Build an m x n table where dp[i][j] is the number of paths to that cell.
  • The first row and first column are all 1 (only one straight-line path).
  • Every other cell is dp[i-1][j] + dp[i][j-1].
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

3. Optimise the Space

  • Each row only depends on the row above, so a single 1-D array suffices.
  • Iterate rows top to bottom, adding the value to its left in place.
  • This drops memory to O(n).
def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[-1]

4. Closed-Form Solution and Complexity

  • Any path makes exactly m - 1 down moves and n - 1 right moves.
  • The count is the binomial coefficient C(m + n - 2, m - 1).
  • Computing it multiplicatively is O(min(m, n)) time and O(1) space.
def unique_paths(m: int, n: int) -> int:
    result = 1
    for i in range(1, min(m, n)):
        result = result * (m + n - 1 - i) // i
    return result

FAQ

See also

Practice Unique Paths online (run code in the browser)Climbing Stairs solution (easy)Fibonacci Number solution (easy)Pascal's Triangle solution (easy)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?