← Create New Paste

Unique Paths in a Grid: How to Talk Through the Classic DP Interview Question

3 views
The "unique paths" problem shows up in coding interviews more often than its simplicity suggests. A robot starts in the top-left corner of an m x n grid and can only move right or down. How many distinct paths lead to the bottom-right corner? Interviewers like it because it rewards clear thinking more than memorization, and because it has several follow-ups that reveal how deeply a candidate understands dynamic programming. Start with the recurrence, out loud The strongest candidates do not jump straight to code. They say something like: "To reach any cell, I must arrive from the cell above or the cell to the left, so the number of ways to reach cell (i, j) is the sum of the ways to reach (i-1, j) and (i, j-1)." That single sentence is the whole insight. The first row and first column each have exactly one path, because you can only keep moving in one direction along them. From there, a 2D table fills naturally in O(m*n) time and space. Say the complexity before the interviewer asks. Show the space optimization A common follow-up is: "Can you use less memory?" Because each row only depends on the row above it, a single array of length n is enough. Iterate row by row and update dp[j] = dp[j] + dp[j-1]. Explaining why this works, that dp[j] still holds the value from the previous row until you overwrite it, is more impressive than the code itself. Mention the math shortcut Every path consists of exactly (m-1) down moves and (n-1) right moves, so the answer is the binomial coefficient C(m+n-2, m-1). Bringing this up shows breadth. Then note the practical caveat: for large grids you need to compute the coefficient carefully to avoid overflow, multiplying and dividing incrementally. Handle the obstacle variant The most frequent extension is "Unique Paths II," where some cells are blocked. The recurrence stays the same, except a blocked cell contributes zero paths. The trap is the first row and column: once an obstacle appears, every cell after it on that edge is unreachable. Candidates who initialize those edges to 1 without checking get the wrong answer, so call out that edge case explicitly. Testing your solution Walk through a 3 x 3 grid by hand (the answer is 6) and a 1 x 1 grid (the answer is 1). Then test an obstacle at the start cell, which should return 0. Interviewers notice when you test edge cases without being prompted. Practicing under real conditions Knowing the recurrence is one thing; explaining it calmly while someone watches you type is another. Many candidates rehearse with mock interviews, and some use tools such as Linkjob AI (https://linkjob.ai), which provides real-time help during job interviews and technical interviews, to stay structured when nerves kick in. Whatever you use, practice narrating your reasoning: the recurrence, the base cases, the optimization, and the tests. That narrative is what turns a correct answer into a strong hire signal.
Created Nov 16, 2026 17:28 Expires Nov 16, 2027 17:28