Skip to content

141 — Unique Paths

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

141 — Unique Paths

LeetCode 62 · Medium. There is a robot on an m x n grid. The robot is initially located at the top-left corner and can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. Return the number of possible unique paths.

🍽️ Intuition

Picture standing at the top-left corner of a city grid where you can only walk south or east. The number of distinct ways to reach any intersection is just the sum of the ways to reach the intersection directly above it and the intersection directly to its left — because every path to here arrived either from above (then stepped down) or from the left (then stepped right), and those two sets of paths never overlap. That's the whole problem: build the grid of "ways to reach here" values, one cell at a time, from two neighbors.

🚩 Pattern-Recognition Cue

"Count the number of paths through a grid, moving only right or down" is the 2-D grid-DP tell: the state is naturally two indices (row, column), and each cell's answer depends only on the cell above it and the cell to its left — no need to look further back than one step in either direction.

🐢 Brute Force

Recurse from the top-left cell, branching into "move right" and "move down" at every step, with no memoization — the same cells get revisited from many different paths.

func uniquePathsBruteForce(_ m: Int, _ n: Int) -> Int {
    func countFrom(_ row: Int, _ col: Int) -> Int {
        if row == m - 1 || col == n - 1 { return 1 }   // last row or last column: exactly one way onward
        return countFrom(row + 1, col) + countFrom(row, col + 1)
    }
    return countFrom(0, 0)
}

// smoke test
print(uniquePathsBruteForce(3, 2))   // 3
print(uniquePathsBruteForce(3, 7))   // 28
print(uniquePathsBruteForce(1, 1))   // 1

Big-O: O(2^(m+n)) time in the worst case — every cell not in the last row/column branches two ways, and the same cells are re-explored along many different paths. O(m + n) space for the recursion stack.

🚀 Optimal

Fill an m x n table where dp[i][j] is the number of ways to reach cell (i, j) — the first row and first column are all 1 (only one way to walk straight along an edge), and every other cell is the sum of its up-neighbor and left-neighbor.

func uniquePaths(_ m: Int, _ n: Int) -> Int {
    var dp = Array(repeating: Array(repeating: 1, count: n), count: m)
    guard m > 1 && n > 1 else { return 1 }

    for i in 1..<m {
        for j in 1..<n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

// smoke test — same cases as the brute force
print(uniquePaths(3, 2))   // 3
print(uniquePaths(3, 7))   // 28
print(uniquePaths(1, 1))   // 1

Big-O: O(m · n) time — every cell is filled exactly once from two already-known neighbors. O(m · n) space for the dp table (collapsible to O(n) with a single rolling row, though the two-dimensional table is kept here to show the grid directly).

🔑 The Key Insight

Both versions ask the exact same question at every cell — "how many ways to get here, given the ways to get to the cell above and the cell to the left?" — but the brute force treats every cell as a fresh sub-problem no matter how many different paths arrive at it, so cells near the top-left get recomputed exponentially many times. The optimal version fills the grid row by row, left to right, so that by the time dp[i][j] is computed, dp[i-1][j] and dp[i][j-1] are already finished, reusable answers. Reusing two already-solved neighbors instead of re-branching from scratch is what turns exponential path-counting into a flat O(m · n) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — the canonical shape here: "where am I" is genuinely two numbers (row and column), and each cell depends only on its up and left neighbors, exactly the grid-path-counting recognition signal called out in chapter 27.
  • Matrix Traversal — the DP table is the grid itself, filled in the same row-by-row, in-bounds-checked style as any matrix traversal.
  • Arrays and Strings — the dp table is a plain 2-D array built with Array(repeating:count:), filled in place.

🧸 Memory Sentence

Unique Paths is the two-neighbors grid: the ways to reach any cell are just the ways to reach the cell above plus the ways to reach the cell to the left, starting from a border of all ones.

✅ Check Your Understanding

  1. Why are the entire first row and first column initialized to 1 rather than 0? What real-world paths does that 1 represent?
  2. Trace uniquePaths(3, 2) by hand-filling the 3x2 table. Which cell holds the final answer, and which two neighboring cells does its value come from?
  3. The brute force's base case fires when row == m - 1 || col == n - 1. Why is an "or" the right condition here rather than "and"?

⬅️ Previous: Partition Equal Subset Sum · Next: Longest Common Subsequence ➡️

Clone this wiki locally