What pattern does Unique Paths use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: 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.

Unique Paths - LeetCode Solution & Explanation

Q: What is the time complexity of Unique Paths?

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.

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

Input: m = 3, n = 7

Output: 28

Starting 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

Recognizing the overlapping subproblems, memoization stores the number of paths to each cell once computed, transforming the exponential recursion into a polynomial-time solution. The problem's structure naturally fits a dynamic programming approach where the solution to a cell is built from solutions to smaller subproblems (its neighbors).

Optimal Approach

Implement 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. For other cells, the function sums the number of paths from the cell above and the cell to the left, caching results to avoid recomputation. This yields an O(m*n) time complexity with O(m*n) space for memoization.

Time

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.

Solution

1class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
      memo = {}
4
      def dp(row, col):
          if row == 0 and col == 0:
              return 1
          if row < 0 or col < 0:
              return 0
          if (row, col) in memo:
              return memo[(row, col)]
          
          memo[(row, col)] = dp(row - 1, col) + dp(row, col - 1)
          return memo[(row, col)]
15
      return dp(m - 1, n - 1)

1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
  public int uniquePaths(int m, int n) {
      Map<String, Integer> memo = new HashMap<>();
7
      return dp(m - 1, n - 1, memo);
  }
10
  private int dp(int row, int col, Map<String, Integer> memo) {
      if (row == 0 && col == 0) {
          return 1;
      }
      if (row < 0 || col < 0) {
          return 0;
      }
      String key = row + "," + col;
      if (memo.containsKey(key)) {
          return memo.get(key);
      }
22
      int result = dp(row - 1, col, memo) + dp(row, col - 1, memo);
      memo.put(key, result);
      return result;
  }
27}

1#include <unordered_map>
2#include <string>
3
4using namespace std;
5
6class Solution {
7public:
8    int uniquePaths(int m, int n) {
9        return dp(m - 1, n - 1);
10    }
11
12private:
13    unordered_map<string, int> memo;
14
15    int dp(int row, int col) {
16        if (row == 0 && col == 0) {
17            return 1;
18        }
19        if (row < 0 || col < 0) {
20            return 0;
21        }
22        string key = to_string(row) + "," + to_string(col);
23        if (memo.find(key) != memo.end()) {
24            return memo[key];
25        }
26
27        memo[key] = dp(row - 1, col) + dp(row, col - 1);
28        return memo[key];
29    }
30};

1var uniquePaths = function(m, n) {
  const memo = new Map();
3
  function dp(row, col) {
      if (row === 0 && col === 0) {
          return 1;
      }
      if (row < 0 || col < 0) {
          return 0;
      }
      const key = row + ',' + col;
      if (memo.has(key)) {
          return memo.get(key);
      }
15
      const result = dp(row - 1, col) + dp(row, col - 1);
      memo.set(key, result);
      return result;
  }
20
  return dp(m - 1, n - 1);
22};

Step-by-Step Solution

1

Implement Base Cases and Memoization Lookup in Recursive Counting

6if row == 0 and col == 0:
7    return 1
8if row < 0 or col < 0:
9    return 0
10if (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.

2

Recursively Compute and Cache Number of Paths for Each Cell

13memo[(row, col)] = dp(row - 1, col) + dp(row, col - 1)
14return memo[(row, col)]

Objective

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.

Key Insight

The number of unique paths to a cell is the sum of unique paths to the cell above and the cell to the left, reflecting the allowed moves. Storing this sum in the memo cache ensures that future calls for this cell return instantly, enabling efficient reuse of computed results and transforming the recursion into a dynamic programming solution.

Interview Quick-Check

Core Logic

The recurrence relation dp(row, col) = dp(row-1, col) + dp(row, col-1) captures the problem's combinatorial structure.

State & Boundaries

Memoizing the computed value before returning ensures each subproblem is solved once.

Complexity

This caching reduces the time complexity from exponential to polynomial.

3

Return the Total Number of Unique Paths from Start to Destination

16	`return dp(m - 1, n - 1)`

Objective

To initiate the recursive computation from the bottom-right cell and return the final count of unique paths.

Key Insight

Starting the recursion from the destination cell (m-1, n-1) triggers the top-down calculation of all subproblems needed to determine the total number of unique paths. This approach naturally builds the solution from the base case upwards, leveraging memoization to efficiently compute the answer.

Interview Quick-Check

Core Logic

Calling dp(m-1, n-1) computes the total unique paths to the destination by recursively summing paths from all reachable cells.

State & Boundaries

The recursion bottoms out at the base case (0,0), ensuring correctness.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 10 Critical

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.

Line 13 Critical

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.

Line 6 Critical

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.

Line 11 Critical

return memo[(row, col)]

Return the cached number of paths if available.

Returning the cached result immediately prunes the recursion tree, ensuring each subproblem is solved once.

Line 3 Core

memo = {}

Initialize a memoization dictionary to cache computed results for subproblems.

This dictionary is essential to store the number of unique paths to each cell, preventing redundant recursive calls and reducing the time complexity from exponential to polynomial.

Line 7 Core

return 1

Return 1 for the base case at the starting cell.

Returning 1 here correctly represents the single path that starts and ends at the origin, enabling the recursive accumulation of paths.

Line 14 Core

return memo[(row, col)]

Return the computed number of paths for the current cell.

Returning the memoized result ensures the recursive calls receive the correct count and that the memo cache is used for future lookups.

Line 16 Core

return dp(m - 1, n - 1)

Start the recursive computation from the bottom-right cell and return the total unique paths.

This call triggers the entire top-down dynamic programming process, ultimately returning the total number of unique paths from the start to the destination.

Line 8 Core

if row < 0 or col < 0:

Check if the current cell indices are out of grid bounds.

Cells outside the grid are invalid and contribute zero paths, which prevents the recursion from exploring invalid states.

Line 9 Core

return 0

Return 0 for out-of-bound cells.

Returning zero here correctly prunes invalid paths and ensures the recursion only counts valid grid positions.

Test Your Understanding

Why is memoization necessary in this recursive solution for counting unique paths?

Memoization prevents redundant calculations by caching the number of paths to each cell, avoiding the exponential explosion of recursive calls and ensuring each subproblem is solved only once.

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

or drill a free problem

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)`

1	`import java.util.HashMap;`
2	`import java.util.Map;`
3
4	`public class Solution {`
5	`public int uniquePaths(int m, int n) {`
6	`Map<String, Integer> memo = new HashMap<>();`
7
8	`return dp(m - 1, n - 1, memo);`
9	`}`
10
11	`private int dp(int row, int col, Map<String, Integer> memo) {`
12	`if (row == 0 && col == 0) {`
13	`return 1;`
14	`}`
15	`if (row < 0 \|\| col < 0) {`
16	`return 0;`
17	`}`
18	`String key = row + "," + col;`
19	`if (memo.containsKey(key)) {`
20	`return memo.get(key);`
21	`}`
22
23	`int result = dp(row - 1, col, memo) + dp(row, col - 1, memo);`
24	`memo.put(key, result);`
25	`return result;`
26	`}`
27	`}`

1	`#include <unordered_map>`
2	`#include <string>`
3
4	`using namespace std;`
5
6	`class Solution {`
7	`public:`
8	`int uniquePaths(int m, int n) {`
9	`return dp(m - 1, n - 1);`
10	`}`
11
12	`private:`
13	`unordered_map<string, int> memo;`
14
15	`int dp(int row, int col) {`
16	`if (row == 0 && col == 0) {`
17	`return 1;`
18	`}`
19	`if (row < 0 \|\| col < 0) {`
20	`return 0;`
21	`}`
22	`string key = to_string(row) + "," + to_string(col);`
23	`if (memo.find(key) != memo.end()) {`
24	`return memo[key];`
25	`}`
26
27	`memo[key] = dp(row - 1, col) + dp(row, col - 1);`
28	`return memo[key];`
29	`}`
30	`};`

1	`var uniquePaths = function(m, n) {`
2	`const memo = new Map();`
3
4	`function dp(row, col) {`
5	`if (row === 0 && col === 0) {`
6	`return 1;`
7	`}`
8	`if (row < 0 \|\| col < 0) {`
9	`return 0;`
10	`}`
11	`const key = row + ',' + col;`
12	`if (memo.has(key)) {`
13	`return memo.get(key);`
14	`}`
15
16	`const result = dp(row - 1, col) + dp(row, col - 1);`
17	`memo.set(key, result);`
18	`return result;`
19	`}`
20
21	`return dp(m - 1, n - 1);`
22	`};`

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)]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Implement Base Cases and Memoization Lookup in Recursive Counting

Recursively Compute and Cache Number of Paths for Each Cell

Return the Total Number of Unique Paths from Start to Destination

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.