Unique Paths
Problem
Given two integers m and n representing the dimensions of a grid, return the number of unique paths from the top-left corner to the bottom-right corner of the grid, moving only down or right at any point.
- 1 ≤ m, n ≤ 100
Example
m = 3, n = 728Starting at the top-left corner, the algorithm counts all possible sequences of moves that reach the bottom-right corner by moving only down or right. For example, one path is moving right 6 times and down 2 times in any order. The recursive function explores these paths by summing the counts of paths from the cell above and the cell to the left, using memoization to avoid redundant calculations. The critical moment is recognizing that the number of paths to a cell equals the sum of paths to its top and left neighbors, and caching these results prevents exponential recomputation.
Approach
Straightforward Solution
A brute-force recursive approach explores all possible paths by moving down or right at each step, leading to an exponential time complexity O(2^(m+n)) due to overlapping subproblems and repeated calculations.
Core Observation
The number of unique paths to any cell in the grid depends solely on the number of unique paths to the cell directly above it and the cell directly to the left of it. This is a fundamental property of grid traversal with restricted moves.
Path to Optimal
PreviewRecognizing the overlapping subproblems, memoization stores the number of paths to each cell once computed, transforming the exponential recursion into a polynomial-time solution…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a top-down recursive function with memoization that returns the number of unique paths to a given cell (row, col). The base case is the starting cell (0, 0) with one path…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(m * n)
Each cell's number of paths is computed once and stored in the memo dictionary. The recursive calls cover all cells in the m x n grid, resulting in O(m*n) total computations.
Space
O(m * n)
The memo dictionary stores the number of paths for each cell in the grid, requiring O(m*n) auxiliary space. The recursion stack depth is at most O(m+n), which is dominated by the memo size.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves counting paths or combinations with overlapping subproblems, use recursion with memoization to cache intermediate results, converting exponential brute-force into efficient polynomial-time solutions.
Solution
| 1 | class Solution:
|
| 2 | def uniquePaths(self, m: int, n: int) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(row, col):
|
| 6 | if row == 0 and col == 0:
|
| 7 | return 1
|
| 8 | if row < 0 or col < 0:
|
| 9 | return 0
|
| 10 | if (row, col) in memo:
|
| 11 | return memo[(row, col)]
|
| 12 |
|
| 13 | memo[(row, col)] = dp(row - 1, col) + dp(row, col - 1)
|
| 14 | return memo[(row, col)]
|
| 15 |
|
| 16 | return dp(m - 1, n - 1) |
Step-by-Step Solution
Implement Base Cases and Memoization Lookup in Recursive Counting
| 6 | if row == 0 and col == 0:
|
| 7 | return 1
|
| 8 | if row < 0 or col < 0:
|
| 9 | return 0
|
| 10 | if (row, col) in memo:
|
| 11 | return memo[(row, col)]
|
Objective
To handle the base conditions for recursion and avoid redundant computations by checking the memo cache.
Key Insight
The base cases anchor the recursion: the starting cell has exactly one path, and cells outside the grid boundaries have zero paths. Checking the memo cache before recursive calls ensures that once a cell's path count is computed, it is reused, preventing exponential recomputation and drastically improving efficiency.
Interview Quick-Check
Core Logic
Base cases define the recursion boundaries: (0,0) returns 1 path, and out-of-bound indices return 0 paths.
State & Boundaries
Memoization lookup at the start of the function avoids recomputing results for cells already processed.
Common Pitfalls & Bugs
Forgetting to check the memo before recursion leads to exponential time complexity due to repeated subproblem evaluations.
Recursively Compute and Cache Number of Paths for Each Cell
To calculate the number of unique paths to the current cell by summing paths from the top and left neighbors, then store the result in memo.
Return the Total Number of Unique Paths from Start to Destination
To initiate the recursive computation from the bottom-right cell and return the final count of unique paths.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if (row, col) in memo:Check if the number of paths to the current cell is already computed and cached.
This memoization lookup is critical to avoid recomputing the same subproblem multiple times, which would otherwise cause exponential time complexity.
memo[(row, col)] = dp(row - 1, col) + dp(row, col - 1)Compute the number of paths to the current cell by summing paths from the top and left neighbors.
This recurrence relation embodies the problem's combinatorial structure: the only ways to reach a cell are from above or from the left, so the total paths are the sum of those two subproblems.
if row == 0 and col == 0:Check if the current cell is the starting point (0,0).
The starting cell has exactly one unique path to itself, serving as the base case that anchors the recursion.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why is memoization necessary in this recursive solution for counting unique paths?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Unique Paths from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Unique Paths drill