Unique Paths - Video Solutions

Problem Overview: You are given an m x n grid. Starting at the top-left cell, you can only move either right or down. The task is to count how many distinct paths lead to the bottom-right cell.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

The grid naturally forms overlapping subproblems. Any cell (i, j) can only be reached from the cell above (i-1, j) or from the left (i, j-1). That means the number of ways to reach a cell equals the sum of those two previous states. Build a 2D DP table where dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize the first row and first column with 1 because there is only one way to move straight right or straight down. Iterate through the grid row by row and fill the table. The final answer sits at dp[m-1][n-1]. This method is easy to reason about and commonly used when learning dynamic programming patterns.

The DP solution can also be optimized to O(n) space by storing only one row. Each position accumulates paths from the left and the current value representing the path from above. The transition logic stays the same but memory drops significantly.

Approach 2: Combinatorial Approach (O(min(m,n)) time, O(1) space)

Reframe the grid as a sequence of moves instead of positions. To reach the bottom-right corner, you must make exactly (m-1) downward moves and (n-1) right moves. The total path length is therefore (m+n-2). The problem becomes choosing where the downward moves appear in that sequence. Mathematically, the number of unique paths equals the binomial coefficient C(m+n-2, m-1) or C(m+n-2, n-1). Compute this efficiently by multiplying and dividing iteratively to avoid factorial overflow. This technique relies on basic math and combinatorics principles.

The combinatorial solution runs in linear time relative to the smaller dimension and uses constant memory. It avoids building a grid entirely and directly computes the number of arrangements of moves.

Recommended for interviews: The dynamic programming approach is the most commonly expected explanation because it demonstrates understanding of state transitions and grid DP patterns. After presenting DP, strong candidates often point out the combinatorial observation as a mathematical optimization. Showing both proves you understand the structure of the problem and can move from brute reasoning to an optimal formula.