LeetCode · #62

Unique Paths Solution

A robot starts at the top-left of an m × n grid and can only move right or down. Return the number of unique paths to the bottom-right corner.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #62

🏗️

Pattern

DP — 2D grid traversal

A robot is at the top-left corner of an m × n grid. It can only move right or down at each step. How many unique paths exist to reach the bottom-right corner?

Example

 Input: m = 3, n = 7 Output: 28 

Constraints

• 1 ≤ m, n ≤ 100 ← dp table fits easily

Section Two · Approach 1

Recursion — O(2^(m+n))

At each cell, branch: go right or go down. Base case: if you're at the last row or last column, there's only 1 way. Recursively sum both branches.

Why it works

Every unique path is a sequence of exactly (m-1) down moves and (n-1) right moves. The recursion explores all interleavings.

Why we can do better

Problem: Massive overlapping subproblems. paths(i,j) is recomputed from both paths(i-1,j) and paths(i,j-1). A 2D DP table computes each cell once: O(m·n). Can further optimize to O(n) space using a single row.

Java — Recursive

 class Solution {
public int uniquePaths(int m, int n) {
if (m == 1 || n == 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

Python — Recursive

 class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1: return 1 return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)

Metric	Value
Time	O(2^(m+n))
Space	O(m+n) call stack

Section Three · Approach 2

DP with 1D Space — O(m·n) time, O(n) space

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Since each row only depends on the current row (left) and previous row (above), we only need a single 1D array, updated left to right.

💡 Mental model: Imagine a city grid with one-way streets: you can only drive east or south. To count routes from home (top-left) to work (bottom-right), notice that at any intersection, routes = routes from the north + routes from the west. The first row and first column each have exactly 1 route (straight line). Fill out the grid intersection by intersection — each cell is the sum of the cell above and to its left.

Algorithm

Create dp[n] filled with 1s (first row: all 1s).
For each row 1 to m-1: for each col 1 to n-1: dp[j] += dp[j-1].
The dp[j] already holds "from above" (previous row), and dp[j-1] is "from left" (already updated this row).
Return dp[n-1].

🎯 When to recognize this pattern:

"Count paths in a grid with restricted moves (right/down only)." This is the foundation for harder grid DP: LC 63 (Unique Paths II — with obstacles), LC 64 (Minimum Path Sum), LC 120 (Triangle).
The signal: 2D grid + only forward moves + count/min/max.

Math alternative:

The answer is C(m+n-2, m-1) — choosing which m-1 of the m+n-2 total moves are "down." For small m,n this is fast, but beware of overflow for large values.
DP is safer and generalizes to obstacles.

Section Four · Trace

Visual Walkthrough

Trace for m=3, n=4.

Unique Paths — 2D DP Grid (3×4)

Section Five · Implementation

Code — Java & Python

Java — 1D DP (space-optimized)

 class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1); // first row: all 1s for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
                dp[j] += dp[j - 1]; // above + left return dp[n - 1];
    }
}

Python — 1D DP (space-optimized)

 class Solution:
def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
for i in range(1, m):
for j in range(1, n):
                dp[j] += dp[j - 1]
return dp[-1]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	O(2^(m+n))	O(m+n)	Exponential — TLE
2D DP table	O(m·n)	O(m·n)	Correct; full table stored
1D DP ← optimal	O(m·n)	O(n)	Single row; in-place update

Combinatorics O(min(m,n)): The answer is C(m+n-2, m-1). Computing this requires only O(min(m,n)) multiplications/divisions, but integer overflow is a concern for large m,n. DP is safer for interviews.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
1×1 grid	`m=1, n=1`	Already at destination. Return 1.
Single row	`m=1, n=5`	Only one path (all right). Return 1.
Single col	`m=5, n=1`	Only one path (all down). Return 1.
Square grid	`m=3, n=3`	dp[2][2]=6. Symmetric.
Large grid	`m=100, n=100`	Result fits in long but may overflow int. Python handles naturally.

⚠ Common Mistake: Starting the inner loop at j=0 instead of j=1. Column 0 is always 1 (only path is straight down). Adding dp[j-1] when j=0 accesses dp[-1] — an out-of-bounds error in Java or wrapping to the last element in Python, corrupting the result.

← Back to DP — 2D problems

LearningTree

LC 62 · Unique Paths — Solution & Explanation | DSA Guide