Unique Paths - Solution & Explanation

Problem Overview: You are given an m x n grid. A robot starts at the top-left cell and can only move either right or down. The goal is to compute how many distinct paths lead to the bottom-right cell.

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

This problem fits classic dynamic programming. Each cell represents the number of ways to reach that position. If the robot can only move right or down, the paths to cell (i, j) must come from either (i-1, j) or (i, j-1). Build a 2D DP table where dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize the first row and first column to 1 because there is only one way to move straight across or straight down. Iterate row by row to fill the table until reaching the bottom-right corner. This approach is intuitive, easy to implement in interviews, and clearly shows the transition relation between states.

Space can be optimized to O(n) by keeping only the current row because each state depends only on the left and the previous row value. This optimization is common in grid DP problems.

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

The robot must make exactly m-1 downward moves and n-1 right moves. That means every valid path is simply an arrangement of these moves. The total number of sequences is choosing positions for either the down or right moves. Mathematically this becomes the binomial coefficient:

C(m+n-2, m-1) or C(m+n-2, n-1).

This observation turns the grid problem into a math and combinatorics problem. Instead of building a DP table, compute the binomial coefficient iteratively using multiplication and division to avoid factorial overflow. Only iterate min(m-1, n-1) times while maintaining the result in a running product.

The combinatorial solution is significantly more memory efficient and faster for large grids since it avoids building the entire DP matrix. However, it requires recognizing the mathematical pattern behind the movement constraints.

Recommended for interviews: Start with the dynamic programming solution. It clearly demonstrates state transitions and grid reasoning, which interviewers expect when they see a matrix path-counting problem. After presenting DP, mention the combinatorial formula as an optimization. Showing both approaches proves you understand the problem structurally and mathematically.