{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Unique Paths – Solution & Complexity

Interview solutions
/
Unique Paths

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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)Add Two Numbers solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?