Unique Paths

Unique Paths

What is this problem about?

The Unique Paths interview question is a classic grid-based challenge. You have a robot placed at the top-left corner of an $m \times n$ grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. You need to calculate the total number of unique paths the robot can take.

Why is this asked in interviews?

This is one of the most famous Dynamic Programming and Combinatorics coding problems, asked by almost every major tech company including Amazon, LinkedIn, and Google. It tests whether a candidate can break a large problem into smaller sub-problems. It also allows for multiple solutions, ranging from recursion (slow) to DP (efficient) to pure math (fastest), giving interviewers a clear look at a candidate's depth of knowledge.

Algorithmic pattern used

There are two main Math, Combinatorics, Dynamic Programming interview patterns.

1. Dynamic Programming: The number of ways to reach cell (i, j) is the sum of the ways to reach the cell above it (i-1, j) and the cell to its left (i, j-1). By filling a 2D table (or even a 1D array to save space), you can find the answer in $O(m*n)$ time.
2. Combinatorics: The robot must take exactly $m-1$ down moves and $n-1$ right moves, for a total of $(m-1) + (n-1)$ moves. The problem is equivalent to choosing which of those total moves will be "down" moves, which is a simple combinations formula: $C(total\_moves, down\_moves)$.

Example explanation

For a $3 \times 2$ grid:

1. DP approach:
   • Top row: [1, 1] (only one way to go right)
   • Second row: [1, 2] (1 from above + 1 from left)
   • Third row: [1, 3] (1 from above + 2 from left)
2. Result: 3 unique paths.
3. Math approach: Total moves = $(3-1) + (2-1) = 3$. Down moves = 2. $C(3, 2) = 3! / (2! * 1!) = 3$.

Common mistakes candidates make

The most common mistake is using simple recursion without memoization, which leads to a time limit exceeded (TLE) error because the same sub-problems are calculated millions of times. Another mistake is integer overflow when calculating the combinations formula with large $m$ and $n$.

Interview preparation tip

Always start with the Dynamic Programming explanation, as it shows you understand the recursive nature of the problem. If the interviewer asks for a more optimal solution, then mention the Combinatorics approach. Understanding both the "how" (DP) and the "why" (Math) is the sign of a top-tier candidate.