Unique Paths

Difficulty: Medium Source: NeetCode

Problem

A robot is located at the top-left corner of an m x n grid. The robot can only move either right or down at any point. The robot is trying to reach the bottom-right corner. 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

Constraints:

• 1 <= m, n <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion — understanding how to break a problem into sub-problems
• 2D Dynamic Programming — building a solution table from base cases
• Combinatorics (optional) — the math shortcut using combinations

1. Brute Force / Recursive

Intuition

From any cell, the robot can come from the cell above or the cell to the left. So the number of unique paths to (i, j) is the sum of paths to (i-1, j) and (i, j-1). The base case is the top row and left column — there’s exactly one way to reach any of those cells (go straight right or straight down). We recurse from the bottom-right corner back to the top-left.

Algorithm

1. Define dfs(i, j) returning number of paths to reach (i, j).
2. If i == 0 or j == 0, return 1 (base case: only one way along edge).
3. Otherwise return dfs(i-1, j) + dfs(i, j-1).
4. Call dfs(m-1, n-1).

Solution

def uniquePaths(m, n):
    def dfs(i, j):
        if i == 0 or j == 0:
            return 1
        return dfs(i - 1, j) + dfs(i, j - 1)

    return dfs(m - 1, n - 1)


print(uniquePaths(3, 7))  # 28
print(uniquePaths(3, 2))  # 3
print(uniquePaths(1, 1))  # 1

Complexity

• Time: O(2^(m+n)) — exponential without memoization
• Space: O(m+n) — recursion stack depth

2. Top-Down DP (Memoization)

Intuition

The brute-force approach recomputes the same cells over and over. For instance dfs(2, 3) might be called dozens of times. We can cache the result of each (i, j) pair so it’s only computed once. This turns the exponential solution into a polynomial one.

Algorithm

1. Create a memo dictionary.
2. In dfs(i, j), return 1 if at an edge, or look up the cache.
3. Otherwise compute dfs(i-1, j) + dfs(i, j-1), store in cache, and return.

Solution

def uniquePaths(m, n):
    memo = {}

    def dfs(i, j):
        if i == 0 or j == 0:
            return 1
        if (i, j) in memo:
            return memo[(i, j)]
        memo[(i, j)] = dfs(i - 1, j) + dfs(i, j - 1)
        return memo[(i, j)]

    return dfs(m - 1, n - 1)


print(uniquePaths(3, 7))  # 28
print(uniquePaths(3, 2))  # 3
print(uniquePaths(1, 1))  # 1

Complexity

• Time: O(m * n)
• Space: O(m * n) — memo table plus stack

3. Bottom-Up DP (Tabulation)

Intuition

Instead of recursing from the end, build a table starting from the top-left. Every cell in the first row and first column is 1 (only one way to get there). For every other cell, dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fill row by row and the answer lands at dp[m-1][n-1].

Algorithm

1. Create a m x n table filled with 1s.
2. For i from 1 to m-1, and j from 1 to n-1:
   • dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. Return dp[m-1][n-1].

Solution

def uniquePaths(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]


print(uniquePaths(3, 7))  # 28
print(uniquePaths(3, 2))  # 3
print(uniquePaths(1, 1))  # 1

Complexity

• Time: O(m * n)
• Space: O(m * n) — can be optimised to O(n) using a single row

Common Pitfalls

Forgetting the base case. If you don’t seed the first row and column with 1s, cells adjacent to the edge compute 0 + 0 = 0 instead of the correct value.

Swapping m and n. The grid is m rows by n columns. Make sure your loop bounds match — range(m) for rows, range(n) for columns.

Off-by-one in the recursive call. We index the grid from (0,0) to (m-1, n-1), so the recursive entry point is dfs(m-1, n-1), not dfs(m, n).