Unique Paths — The Grid DP Problem Every FAANG Interview Expects You to Know

Problem Statement#

Given an m x n grid, a robot starts at the top-left corner (0, 0) and wants to reach the bottom-right corner (m-1, n-1). The robot can only move right or down at any point. Return the number of distinct paths.

Constraints:

• 1 <= m, n <= 100

Example 1:

Input:  m = 3, n = 7
Output: 28

Example 2:

Input:  m = 3, n = 2
Output: 3
Explanation: Three paths exist:
  Right -> Down -> Down
  Down -> Right -> Down
  Down -> Down -> Right

Example 3:

Input:  m = 1, n = 1
Output: 1
Explanation: Already at the destination — one path (do nothing).

Why This Problem Matters#

Unique Paths is the entry point to the entire 2D grid DP category. Amazon uses it in nearly every SDE interview loop, and Google includes it as a warm-up before harder grid problems like Minimum Path Sum and Dungeon Game. Understanding this problem deeply is not optional — it is the infrastructure on which every harder grid DP is built.

The problem teaches the most important DP principle: optimal substructure through spatial decomposition. The number of ways to reach any cell is exactly the sum of ways to reach the cell above it and the cell to its left, because those are the only two directions you can arrive from. That two-predecessor recurrence is identical to Pascal's triangle and appears in dozens of other DP problems.

Interviewers also love this problem because it has a clean mathematical shortcut (combinatorics) alongside the DP approach. If you know only the DP and not the combinatorics insight, you expose a gap. Master both.

The Core Insight#

Define dp[i][j] as the number of distinct paths from (0, 0) to (i, j).

State: The number of ways to reach cell (i, j) only depends on how many ways you could reach (i-1, j) (came from above) and (i, j-1) (came from left).

Base cases:

• Every cell in the first row has exactly 1 path — you can only move right the whole time: dp[0][j] = 1 for all j.
• Every cell in the first column has exactly 1 path — only move down: dp[i][0] = 1 for all i.

Recurrence:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Answer: dp[m-1][n-1]

Space optimization: Each row only depends on the previous row and the current row being filled left-to-right. A single 1D array of length n suffices: update dp[j] += dp[j-1] for each row, accumulating left-to-right.

Combinatorics insight: The robot makes exactly (m-1) down moves and (n-1) right moves in some order — (m+n-2) total. The answer is choosing which (n-1) steps are rightward: C(m+n-2, n-1).

Building the DP Solution#

Step 1 — Recursive (no memoization, exponential):

def uniquePaths(m, n):
    if m == 1 or n == 1:
        return 1
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)

This recomputes the same subproblems exponentially. For m=3, n=7 it is already slow.

Step 2 — Top-down with memoization:

from functools import lru_cache
 
def uniquePaths(m, n):
    @lru_cache(None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 1
        return dp(i-1, j) + dp(i, j-1)
    return dp(m-1, n-1)

Time: O(m * n), Space: O(m * n). Correct, but uses call stack.

Step 3 — Bottom-up tabulation (2D):

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]

Step 4 — Space-optimized 1D: Only the previous row is needed at each step. Update in place, left-to-right.

Visual Dry Run#

Input: m = 3, n = 3

Initial state — borders are all 1:

Fill row i=1:

• dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
• dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3

Fill row i=2:

• dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
• dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

Final DP table:

1D rolling array trace (same input):

• Init: dp = [1, 1, 1]
• Row 1: j=1 → dp[1] = 1+1 = 2; j=2 → dp[2] = 2+1 = 3 → dp = [1, 2, 3]
• Row 2: j=1 → dp[1] = 2+1 = 3; j=2 → dp[2] = 3+3 = 6 → dp = [1, 3, 6]
• Return dp[2] = 6

Optimized Solution#

Python#

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 1D rolling array: dp[j] = paths to column j in current row
        dp = [1] * n  # first row: only one way to reach each cell
 
        for _ in range(1, m):
            for j in range(1, n):
                # dp[j] still holds the value from the row above
                # dp[j-1] is the freshly computed value from the left
                dp[j] += dp[j - 1]
 
        return dp[n - 1]

JavaScript#

var uniquePaths = function(m, n) {
    const dp = new Array(n).fill(1);
 
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            // dp[j] (above) + dp[j-1] (left, already updated this row)
            dp[j] += dp[j - 1];
        }
    }
 
    return dp[n - 1];
};

Complexity Analysis#

The 1D DP approach is the expected answer. The combinatorics approach impresses but requires explaining the mathematical derivation.

Common Mistakes#

1. Initializing the DP table to 0 without setting border cases. The first row and column must all be 1. Forgetting this leaves the entire grid as 0 because every cell depends on its top and left neighbors.

2. Confusing m (rows) and n (columns). A 1D rolling array has length n (columns), not m (rows). Getting this backwards produces wrong answers for non-square grids.

3. Running the 1D update in the wrong direction. For unique paths, dp[j] += dp[j-1] works left-to-right because you want to accumulate the running count. Unlike 0/1 knapsack (right-to-left), here we deliberately propagate the count forward.

4. Off-by-one in the loop range. The outer loop runs range(1, m) (row 0 is already initialized). The inner loop runs range(1, n). Starting either at 0 overwrites initialized border values.

5. Integer overflow in the combinatorics formula. C(m+n-2, n-1) can overflow a 32-bit integer in C++ or Java for large inputs. Use 64-bit arithmetic or Python's arbitrary-precision integers. Mention this explicitly in interviews when presenting the math solution.

6. Dividing by zero in manual factorial computation. When n = 1, n-1 = 0 and 0! = 1 — no division by zero, but some manual implementations fail here. Use math.comb in Python or handle the edge case explicitly.

Interview Tips#

• Start by confirming movement directions — "Can we only move right and down?" — then state the recurrence immediately.
• Narrate the base case reasoning: "The first row and column each have exactly one way to reach any cell — you must travel entirely right or entirely down."
• Offer the 1D optimization proactively without being asked. It shows you think about space efficiency.
• Mention the combinatorics shortcut at the end: "There's also an O(1) space, O(min(m,n)) time math solution using combinations." This turns a routine problem into a discussion about algorithm design.
• For follow-ups with obstacles, say: "The structure stays the same — wherever there's an obstacle, we zero out that cell, and the recurrence propagates the block automatically."

Follow-up Questions#

Q: What if the grid has obstacles? (LC 63) Wherever grid[i][j] == 1, set dp[j] = 0. All cells reachable only through that blocked cell also become 0 automatically via the recurrence.

Q: What if you need the actual paths, not just the count? Backtrack from (m-1, n-1) — at each step, move toward whichever neighbor (above or left) has a count greater than 0. The number of full paths is exponential, so only feasible for small grids.

Q: What if movement is in all 4 directions? Standard 2D DP breaks because dependencies become circular. You need BFS or DFS with a visited set; recurrence-based DP does not apply.

Q: Give the O(1) space solution. from math import comb; return comb(m + n - 2, n - 1). Every path is a permutation of (m-1) down steps and (n-1) right steps chosen from (m+n-2) total.

Q: What if costs are attached to each cell and you need minimum-cost path? (LC 64) Switch from counting paths to minimizing sums: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Q: What if the grid is very large (m, n up to 10^9)? The combinatorics formula C(m+n-2, n-1) computes in O(min(m,n)) time using Lucas' theorem for modular arithmetic. The DP table approach is infeasible at that scale.

Key Takeaways#

• dp[i][j] = dp[i-1][j] + dp[i][j-1] is the foundational grid DP recurrence — memorize it as deeply as you memorize Fibonacci.
• The first row and column are always 1 because there is only one direction you can reach them from.
• A 1D rolling array compresses O(m * n) space to O(n) by updating left-to-right within each row.
• The combinatorics shortcut C(m+n-2, n-1) emerges from counting permutations of down/right moves — this connection to combinatorics is worth explaining to interviewers.
• This pattern extends directly to LC 63 (obstacles), LC 64 (min path sum), LC 174 (dungeon game), and LC 931 (falling path sum) — the state changes but the structure is identical.
• Unique Paths is a FAANG staple: Amazon asks it almost universally; Google uses it as a warm-up for harder grid problems.