Unique Paths in Grid: Complete Solution Guide

1. Introduction and Core Concepts

Unique paths in grid is one of the most foundational problems in dynamic programming and combinatorial optimization. The classic formulation is deceptively simple: given an m x n grid, a robot starts at the top-left corner (0, 0) and must reach the bottom-right corner (m-1, n-1). The robot can only move either down or right at any point in time. How many unique paths exist from start to finish? Despite its simplicity, this problem encapsulates the core principles that power much more complex algorithms used in routing, scheduling, and resource allocation.

At its heart, unique paths in grid is a counting problem on a directed acyclic graph (DAG). Each cell in the grid represents a node, and edges exist only to the right and down neighbors. Because movement is restricted and no cycles are possible, the total number of paths can be derived systematically without exhaustive enumeration. This structure makes it an ideal introduction to dynamic programming, as it clearly demonstrates optimal substructure and overlapping subproblems without the additional complexity of optimization objectives.

Understanding unique paths in grid matters far beyond coding interviews. The same grid-based path counting logic underlies warehouse robot navigation, VLSI chip routing, bioinformatics sequence alignment, and even version control diff algorithms. Mastering this problem builds intuition for two-dimensional DP, state transition design, and space optimization techniques that recur in advanced problems like minimum path sum, dungeon game, and edit distance. For any engineer preparing for technical interviews or building real-world systems that involve constrained movement on a lattice, this problem is an essential building block.

Problem Statement and Constraints

The standard unique paths in grid problem (LeetCode 62) defines the input as two integers m and n, where 1 <= m, n <= 100. The robot may only move down or right. The goal is to return the number of unique paths. In the variant with obstacles (LeetCode 63), the input is a 2D array obstacleGrid where 1 represents a blocked cell and 0 represents a free cell. The robot cannot pass through obstacles, which introduces conditional transitions and edge case handling.

A key insight is that any valid path from (0,0) to (m-1, n-1) must consist of exactly (m-1) down moves and (n-1) right moves, in any order, for a total of (m+n-2) moves. This observation connects the dynamic programming solution to a pure combinatorial solution using binomial coefficients, providing a powerful cross-check and an O(1) space alternative when no obstacles are present.

Why Dynamic Programming Is the Natural Fit

Dynamic programming is the natural paradigm for unique paths in grid because the number of ways to reach a cell (i, j) depends only on the number of ways to reach its top neighbor (i-1, j) and its left neighbor (i, j-1). This local dependency means the global solution can be built incrementally from smaller subproblems. Brute-force recursion would recompute the same subproblems exponentially many times, while DP memoizes or tabulates results to achieve polynomial time. This efficiency gain from exponential to polynomial is the central lesson of the problem.

2. How It Works

The mechanism behind unique paths in grid rests on two fundamental properties of dynamic programming: optimal substructure and overlapping subproblems. Optimal substructure means the solution to the larger problem can be constructed from solutions to its subproblems. For a cell (i, j), any path that ends there must have come from either (i-1, j) from above or (i, j-1) from the left. Therefore, dp[i][j] = dp[i-1][j] + dp[i][j-1]. This recurrence relation is the engine of the entire algorithm.

Overlapping subproblems become evident when you draw the recursion tree for a small grid, such as 3x3. The number of ways to reach (1,1) is needed to compute both (1,2) and (2,1), and a naive recursive approach will compute it twice. As the grid grows, the number of overlapping calls explodes exponentially. DP eliminates this redundancy by storing the result for each cell after its first computation and reusing it, transforming an exponential search into a linear scan over the grid.

The base cases anchor the recurrence. The starting cell dp[0][0] = 1, representing one way to be at the start without moving. The entire first row and first column are also 1, because there is only one way to reach any cell in the top row (by moving right repeatedly) and one way to reach any cell in the leftmost column (by moving down repeatedly), assuming no obstacles. Once these boundaries are initialized, the rest of the table can be filled row by row or column by column.

State Definition and Transition

Formally, we define dp[i][j] as the number of unique paths from (0,0) to (i,j). The state transition is dp[i][j] = dp[i-1][j] + dp[i][j-1] for i > 0 and j > 0. With obstacles, the transition becomes conditional: if obstacleGrid[i][j] == 1, then dp[i][j] = 0, else dp[i][j] = dp[i-1][j] + dp[i][j-1] where the terms are zero if the neighbor is out of bounds or blocked. This conditional logic is what makes the obstacle variant more error-prone and interview-relevant.

Combinatorial Perspective

From a combinatorics viewpoint, the problem is equivalent to choosing positions for down moves among total moves. The total number of paths without obstacles is C(m+n-2, m-1) or C(m+n-2, n-1), which is the binomial coefficient. For a 3x7 grid, this is C(8,2) = 28. This formula yields an O(min(m,n)) time solution using iterative multiplication and division, and it highlights that DP is not the only way to count paths when movement is unrestricted. However, the combinatorial approach breaks down when obstacles are introduced, where DP remains robust.

Graph Traversal Analogy

Another way to understand the mechanism is to view the grid as a DAG and count paths using topological order. Since edges only go right and down, a simple row-major traversal is already topologically sorted. Each node's path count is the sum of its predecessors' counts. This perspective generalizes to more complex movement sets, such as allowing diagonal moves or knight moves, where the recurrence simply expands to include more predecessors.

3. Implementation

Implementing unique paths in grid in Python offers several approaches that trade off clarity, time, and space. Below are four canonical implementations, from the exponential brute force to the optimal space-optimized DP and the combinatorial solution. All code is written for clarity and includes detailed comments.

Approach 1: Pure Recursion (Brute Force)

This implementation directly translates the recurrence into recursion without memoization. It is intuitive but has exponential time complexity and will time out for grids larger than about 15x15. It serves as a baseline to understand why optimization is needed.

def unique_paths_recursive(m: int, n: int) -> int:
    """
    Brute force recursion for unique paths in grid.
    m: number of rows, n: number of columns
    Returns number of paths from (0,0) to (m-1, n-1)
    Time: O(2^(m+n)), Space: O(m+n) recursion stack
    """
    def dfs(i, j):
        # Base case: reached origin, one valid path found
        if i == 0 and j == 0:
            return 1
        # Out of bounds, no path
        if i < 0 or j < 0:
            return 0
        # Recurrence: paths from top + paths from left
        return dfs(i - 1, j) + dfs(i, j - 1)
    
    return dfs(m - 1, n - 1)

# Example: 3x2 grid should return 3
print(unique_paths_recursive(3, 2))

Approach 2: Top-Down Memoization

Memoization caches the result of each subproblem (i, j) in a dictionary or 2D array. This converts the exponential recursion into O(m*n) time while retaining the recursive structure, which many developers find easier to reason about.

def unique_paths_memo(m: int, n: int) -> int:
    """
    Top-down DP with memoization.
    Uses a 2D memo table to avoid recomputation.
    """
    memo = [[-1 for _ in range(n)] for _ in range(m)]

    def dfs(i, j):
        if i == 0 and j == 0:
            return 1
        if i < 0 or j < 0:
            return 0
        if memo[i][j] != -1:
            return memo[i][j]
        # Store result before returning
        memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1)
        return memo[i][j]

    return dfs(m - 1, n - 1)

def unique_paths_with_obstacles_memo(obstacleGrid) -> int:
    """
    Memoized version handling obstacles.
    obstacleGrid[i][j] == 1 means blocked.
    """
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = {}

    def dfs(i, j):
        if i < 0 or j < 0 or obstacleGrid[i][j] == 1:
            return 0
        if i == 0 and 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)

Approach 3: Bottom-Up Tabulation (2D DP)

Tabulation builds the DP table iteratively from base cases. This is the most common interview solution because it is iterative, avoids recursion limits, and clearly shows the O(m*n) time and space complexity. It also handles obstacles naturally.

def unique_paths_tabulation(m: int, n: int) -> int:
    """
    Bottom-up 2D DP table.
    dp[i][j] = number of paths to reach (i, j)
    """
    # Initialize DP table with zeros
    dp = [[0 for _ in range(n)] for _ in range(m)]
    
    # Base cases: first row and first column are all 1s
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    # Fill rest of table using recurrence
    for i in range(1, m):
        for j in range(1, n):
            # dp[i][j] = from top + from left
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    return dp[m - 1][n - 1]

def unique_paths_obstacles_tabulation(obstacleGrid) -> int:
    """
    Tabulation with obstacles. Handles blocked cells.
    """
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Initialize start cell
    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
    
    # Fill first column
    for i in range(1, m):
        dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i - 1][0]
    
    # Fill first row
    for j in range(1, n):
        dp[0][j] = 0 if obstacleGrid[0][j] == 1 else dp[0][j - 1]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    return dp[m - 1][n - 1]

Approach 4: Space-Optimized 1D DP and Combinatorial

Since dp[i][j] only depends on the previous row and current row's left cell, the 2D table can be compressed to a 1D array. This reduces space from O(m*n) to O(n). The combinatorial solution goes even further, using O(1) space when no obstacles exist.

def unique_paths_optimized(m: int, n: int) -> int:
    """
    Space-optimized DP using 1D array.
    Time: O(m*n), Space: O(n)
    dp[j] represents number of paths to current row's column j
    """
    # Ensure n is the smaller dimension to minimize space
    if m < n:
        m, n = n, m
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            # dp[j] = dp[j] (from top, old value) + dp[j-1] (from left)
            dp[j] = dp[j] + dp[j - 1]
    
    return dp[n - 1]

def unique_paths_combinatorial(m: int, n: int) -> int:
    """
    Combinatorial solution using binomial coefficient.
    Total moves = m+n-2, choose (m-1) down moves.
    Time: O(min(m,n)), Space: O(1)
    """
    import math
    # Use math.comb in Python 3.8+ for exact integer arithmetic
    # For manual implementation to avoid overflow:
    total = m + n - 2
    k = min(m - 1, n - 1)  # Choose smaller k for efficiency
    result = 1
    for i in range(1, k + 1):
        # result = result * (total - k + i) // i
        result = result * (total - i + 1) // i
    return result

# Example checks
print(unique_paths_optimized(3, 7))      # Expected 28
print(unique_paths_combinatorial(3, 7))  # Expected 28

4. Step-by-Step Example

To solidify the DP intuition, let us walk through a concrete 3x3 grid without obstacles. The goal is to compute the number of unique paths from (0,0) to (2,2). We will build the dp table step by step using the bottom-up approach. This example is small enough to verify manually yet large enough to show the pattern.

We initialize a 3x3 dp table with zeros. First, we set the base cases: dp[0][0] = 1. The first row dp[0][j] = 1 for all j, because you can only move right to stay in the first row. Similarly, the first column dp[i][0] = 1 for all i, because you can only move down to stay in the first column. After initialization, the table looks like:

Row 0: [1, 1, 1]
Row 1: [1, 0, 0]
Row 2: [1, 0, 0]

Now we fill the interior cells. For cell (1,1), we apply dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2. This means there are two ways to reach the center: Right then Down, or Down then Right. Next, cell (1,2): dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3. The three paths to (1,2) are RRD, RDR, DRR in terms of moves from the origin. Next, cell (2,1): dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3, symmetric to (1,2).

Finally, the destination cell (2,2): dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6. The six unique paths are: RRDD, RDRD, RDDR, DRRD, DRDR, DDRR. The completed table is:

Row 0: [1, 1, 1]
Row 1: [1, 2, 3]
Row 2: [1, 3, 6]

Notice how each interior value is the sum of the cell above and the cell to the left, creating a pattern similar to Pascal's triangle. If we add an obstacle at (1,1), the computation changes: dp[1][1] becomes 0, then dp[1][2] = dp[0][2] + 0 = 1, dp[2][1] = 0 + dp[2][0] = 1, and dp[2][2] = 1 + 1 = 2. The obstacle eliminates four of the six paths, leaving only those that go around the blocked center via the edges.

Tracing with 1D Optimization

Using the 1D optimized array, we start with dp = [1, 1, 1]. For i=1 (second row), we iterate j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2, so dp becomes [1, 2, 1]. Then j=2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3, dp becomes [1, 2, 3]. For i=2 (third row), j=1: dp[1] = 2 + 1 = 3, dp = [1, 3, 3]. j=2: dp[2] = 3 + 3 = 6, dp = [1, 3, 6]. The final answer dp[2] = 6 matches the 2D result, demonstrating how the 1D array overwrites values in place while preserving the needed previous-row information in dp[j].

5. Complexity Analysis

Complexity analysis for unique paths in grid reveals a dramatic improvement from exponential to polynomial when moving from brute force to dynamic programming, and further to near-constant space with combinatorial methods. Understanding these trade-offs is critical for selecting the right implementation under constraints such as large grid sizes, memory limits, or the presence of obstacles.

The brute-force recursive solution explores two branches at each step until it hits the boundary, resulting in a recursion tree with approximately 2^(m+n) nodes. The depth of the recursion stack is m+n, but the total work is exponential, making it infeasible for m, n > 20. Memoization and tabulation both visit each of the m*n cells exactly once, performing O(1) work per cell, yielding O(m*n) time. The space differs: memoization uses O(m*n) for the memo table plus O(m+n) recursion stack, while tabulation uses O(m*n) for the table but no recursion overhead.

Space optimization reduces the memory footprint to O(min(m,n)) by keeping only one row or column at a time. This is achievable because the transition only needs the previous row. For the obstacle-free case, the combinatorial solution computes the binomial coefficient in O(min(m,n)) time and O(1) space using iterative multiplication with division at each step to prevent overflow, which is optimal for large grids where m and n are up to 10^9 but cannot handle obstacles.

Best, Average, and Worst Case Nuances

For DP approaches, best, average, and worst cases are identical in terms of asymptotic complexity because every cell must be visited regardless of input values, except when early termination is possible. For example, if the start or end cell is blocked in the obstacle variant, the answer is immediately 0 in O(1) time. Similarly, if an entire row or column is blocked, DP can short-circuit. However, these are input-specific optimizations and do not change the worst-case bound. The combinatorial method's time depends only on min(m,n), so a 1x1000 grid is O(1) while a 500x500 grid is O(500).

Integer Overflow and Large Grids

The number of paths grows extremely quickly. For a 100x100 grid, the result is approximately 9e58, far exceeding 64-bit integer limits. In Python, integers have arbitrary precision, so overflow is not an issue, but in languages like Java or C++, you must use 64-bit longs or modulo arithmetic (often 1e9+7). When implementing the combinatorial formula, intermediate multiplication can overflow even if the final result fits, so dividing at each step is essential: result = result * (n - i + 1) // i.

6. Variations and Optimizations

The basic unique paths in grid problem has spawned numerous variations that test deeper DP skills. The most common is Unique Paths II, which introduces obstacles. Other variants include allowing different move sets, finding minimum path sums, counting paths with modulo, and handling large grids with combinatorial math. Each variation requires a slight adjustment to the state transition or initialization.

One powerful optimization is using combinatorics with obstacles via inclusion-exclusion, though it is complex. A more practical optimization is the 1D DP compression already discussed. Another is using BFS or DFS with memoization when the grid is sparse or when obstacles are few, as you can prune blocked regions early. For very large grids where m*n is too large to iterate (e.g., m, n up to 1e9), the combinatorial method is the only feasible approach, but it only works without obstacles.

Another interesting variation is Unique Paths III, where you must visit every non-obstacle square exactly once. This is a Hamiltonian path counting problem, which is NP-hard and requires backtracking with bitmask DP, fundamentally different from the simple DP of the original problem. Recognizing when a variation changes the complexity class is a key interview skill.

Handling Obstacles Efficiently

When obstacles are present, the initialization of the first row and column must stop propagating 1s after the first obstacle. For example, if obstacleGrid[0][2] == 1, then dp[0][2] = 0 and all cells to its right in the first row must also be 0, because you cannot jump over the obstacle. The same applies to the first column. Many incorrect implementations forget this and incorrectly set dp[0][j] = 1 for all j beyond an obstacle.

Alternative Move Sets

Some variations allow moves in four directions, diagonal moves, or knight moves. If moves include up and left, cycles become possible, and the problem is no longer a DAG, requiring different techniques like DP with visited sets or BFS. If diagonal moves are allowed (down, right, and diagonal down-right), the recurrence becomes dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], which counts Delannoy numbers. Understanding how to adapt the recurrence to new move sets demonstrates true mastery of the pattern.

Modulo and Large Number Handling

In competitive programming, you are often asked to return the answer modulo 1e9+7 to handle large numbers. The DP transition then becomes dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD. For combinatorial solutions, you need modular inverses using Fermat's Little Theorem to compute division under modulo, which adds number theory to the problem.

7. Real-World Applications

While unique paths in grid appears as an abstract puzzle, its underlying model of counting constrained paths on a lattice appears in numerous real-world systems. Any domain where movement is restricted to a grid and decisions are sequential can be modeled as a variant of this problem.

In robotics and autonomous navigation, warehouse robots from companies like Amazon and Ocado navigate grid-like storage layouts. Counting paths helps estimate route diversity and congestion. If a robot can only move forward and turn right due to aisle constraints, the number of unique paths informs path planning algorithms and helps evaluate the robustness of the layout to blockages. When an aisle is blocked (an obstacle), the DP with obstacles directly models the alternative route count.

In bioinformatics, sequence alignment algorithms such as Needleman-Wunsch and Smith-Waterman use a 2D DP grid where rows represent one DNA sequence and columns represent another. Moving right corresponds to a gap in the first sequence, moving down to a gap in the second, and diagonal moves to matches or mismatches. Counting paths in this grid corresponds to counting possible alignments, and the DP structure is identical to unique paths but with weighted transitions.

In network routing and VLSI design, chip interconnects are often routed on a Manhattan grid where wires can only run horizontally or vertically. Counting unique paths helps estimate routing congestion and alternative wiring options when certain grid cells are blocked by existing components. Similarly, in urban planning, counting pedestrian or vehicle routes through a city grid with blocked streets (construction zones) uses the same DP logic to model traffic flow alternatives.

Web Servers and Database Query Planning

In distributed systems, a request may pass through multiple stages or shards arranged in a grid-like pipeline. Counting unique paths through healthy nodes helps estimate system reliability and load distribution. Database query optimizers use DP over join orderings that can be visualized as a grid, where each path represents a different join sequence, and obstacles represent invalid or high-cost joins that should be pruned.

Image Processing and Computer Vision

Seam carving, an image resizing algorithm, uses a DP grid to find the lowest-energy vertical or horizontal seam to remove. The DP transition is similar to unique paths but minimizes energy instead of counting paths. The grid represents pixel energies, and the path counting logic is adapted to find optimal seams, demonstrating how the same lattice DP framework supports both counting and optimization objectives.

8. Comparison with Alternatives

Choosing the right approach for unique paths in grid depends on constraints such as obstacle presence, grid size, memory limits, and whether you need to enumerate paths or just count them. The table below compares the major alternatives across multiple dimensions to guide decision-making in interviews and production systems.

For most interview settings, bottom-up tabulation is the safest answer because it is iterative, easy to explain, and handles obstacles. If the interviewer asks for space optimization, the 1D DP shows deeper understanding. The combinatorial solution is a strong follow-up when the interviewer confirms no obstacles are present, demonstrating mathematical insight. DFS with memoization is useful when the grid is not dense or when movement is not strictly right/down, as recursion naturally handles irregular graphs.

BFS or DFS enumeration that actually generates all paths is never appropriate for counting alone, because the number of paths grows exponentially and enumeration will be infeasible for even moderate grids. However, if the problem asks to list all paths rather than count them, backtracking becomes necessary, and the complexity inevitably becomes exponential in the output size.

When to Choose Which Approach

Use 2D DP when clarity and obstacle handling are priorities and memory is not constrained. Use 1D DP when memory is limited or when you want to impress the interviewer with optimization. Use combinatorial when the grid is huge and obstacle-free, or when you need O(1) space. Use memoization when the problem is presented recursively or when the grid is sparse and many cells are unreachable, as memoization will only compute reachable states.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing unique paths in grid, especially under interview pressure. Recognizing these pitfalls and following best practices can prevent off-by-one errors, incorrect obstacle handling, and integer overflow issues.

The most frequent mistake is incorrect initialization of the first row and column when obstacles are present. Many candidates set dp[0][j] = 1 for all j if obstacleGrid[0][j] == 0, forgetting that a single obstacle blocks all subsequent cells in that row. The correct logic is to iterate and set dp[0][j] = 0 if any previous cell in the row was blocked, or more simply, dp[0][j] = dp[0][j-1] if current cell is not blocked, else 0. The same applies to the first column.

Another common error is forgetting to check if the start or end cell is blocked. If obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1, the answer is immediately 0, and no DP computation is needed. Failing to handle this edge case leads to incorrect results where the DP table incorrectly counts paths that start or end on a blocked cell.

Off-by-one errors in loop bounds are also prevalent. The DP table is m x n, but loops must start from 1 and go to m-1 and n-1 inclusive. Using range(1, m) and range(1, n) is correct in Python, but some developers mistakenly use range(m) and then access dp[i-1][j] when i=0, causing index errors or incorrect base case overwrites. Always separate base case initialization from the main DP loop.

Best Practices for Robust Code

• Validate inputs early: Check for empty grid, blocked start/end, and single-row or single-column grids before DP.
• Use meaningful variable names: Use m, n, dp, obstacleGrid consistently to avoid confusion between rows and columns.
• Prefer iterative over recursive for large grids: Iterative DP avoids recursion depth limits in Python (default ~1000) which can be exceeded for grids larger than 500x500 with memoization.
• Handle large numbers with modulo: If the problem statement mentions large grids, always ask whether the answer should be returned modulo 1e9+7.
• Test with small examples: Verify with 1x1, 1xN, Nx1, 2x2, and 3x3 grids, both with and without obstacles, to catch edge cases.
• Optimize space when asked: Mention the 1D optimization even if you implement 2D, to show awareness of trade-offs.

Debugging Tips

When debugging, print the DP table after each row to visually verify the propagation of path counts. For obstacle variants, print both the obstacle grid and DP table side by side to ensure blocked cells are correctly zeroed. If your answer is off by one, check whether you initialized dp[0][0] correctly and whether you are double-counting the start cell. If your answer is zero unexpectedly, check whether an early obstacle is incorrectly zeroing the entire table.

10. Interview Questions

Unique paths in grid is a staple of technical interviews because it tests DP fundamentals, edge case handling, and optimization skills. Below are five common interview questions, ranging from the basic problem to advanced variations, with guidance on how to approach each.

Q1: Unique Paths (LeetCode 62) — No Obstacles

Question: Given m and n, return the number of unique paths from top-left to bottom-right moving only down or right. How would you solve it in O(m*n) time and O(n) space?

Approach: Explain the 2D DP recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] with base cases of 1 for first row/column, then optimize to 1D by noting only previous row is needed. Mention the combinatorial alternative C(m+n-2, m-1) as a follow-up. Provide the 1D code and discuss why it works. This tests basic DP and space optimization.

Q2: Unique Paths II (LeetCode 63) — With Obstacles

Question: Given obstacleGrid, count paths that avoid obstacles. What if the starting cell is blocked?

Approach: Emphasize conditional transition: dp[i][j] = 0 if blocked else dp[i-1][j] + dp[i][j-1]. Highlight initialization nuance for first row/column where an obstacle blocks all subsequent cells. State that if obstacleGrid[0][0] == 1, return 0 immediately. This tests attention to edge cases and conditional DP.

Q3: Minimum Path Sum (LeetCode 64) — Optimization Variant

Question: Each cell has a cost grid[i][j]. Find the path from top-left to bottom-right that minimizes the sum of costs, moving only down or right.

Approach: This is the optimization version of unique paths. The recurrence becomes dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The structure is identical, but the operation changes from sum to min-plus. Explain that counting vs. optimizing are two sides of the same DP coin. This tests ability to adapt the DP pattern to a new objective.

Q4: Unique Paths with Diagonal Moves

Question: If the robot can also move diagonally down-right, how does the recurrence change? How many paths in a 3x3 grid?

Approach: The recurrence expands to dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]. For 3x3, the answer becomes 13 instead of 6 (Delannoy numbers). Discuss how adding moves increases connectivity and how the DP framework naturally extends by adding predecessors. This tests generalization ability.

Q5: Count Paths Modulo 1e9+7 for Large Grids

Question: m, n can be up to 1e9, but there are no obstacles. How do you compute the answer without O(m*n) time?

Approach: Use the combinatorial formula C(m+n-2, m-1) % MOD with modular arithmetic. Explain that you need to compute factorials modulo MOD and use modular inverses via fast exponentiation (Fermat's Little Theorem) because division under modulo requires multiplying by the inverse. Mention Lucas theorem if MOD is small and n is huge. This tests combinatorics and number theory beyond basic DP.

Preparing answers for these five questions covers the full spectrum of unique paths in grid interview scenarios, from implementation to optimization to mathematical insight. Practice coding each variant without looking at notes, and always articulate the time and space complexity before writing code.