Skip to content

Volume ITechnology

4.24.1 — Unique Paths ​

LeetCode 62 · Medium · ★ Blind 75

The problem ​

A robot starts at the top-left of an m × n grid and must reach the bottom-right, moving only right or down. How many distinct paths are there?

m = 3, n = 7   →  28
m = 3, n = 2   →  3

Constraints:

  • 1 <= m, n <= 100
  • The answer will be less than or equal to 2 * 10^9 (fits in a standard 32-bit integer).

Plain-English Restatement: Imagine you are playing a board game on a grid where you can only move your piece rightwards or downwards. You start at the top-left corner and want to find every possible unique sequence of moves that lands you at the bottom-right corner. Two paths are considered distinct if they differ by even a single move (e.g., going Right-Down is different from going Down-Right).

Brute Force Approach: The naive way to solve this is to simulate the robot's movement using Recursion (or Depth-First Search). From any cell (r, c), you would recursively call your function to go right (r, c+1) and down (r+1, c).

  • Time Complexity: O(2^{m+n}). At almost every step, you branch into 2 possibilities. A path takes exactly (m-1) + (n-1) steps, so the recursion tree grows exponentially. For a 100x100 grid, 2^{200} is astronomically large and will instantly Time Out.
  • Why it's wasteful: The recursion evaluates the exact same cells multiple times. If you go Right then Down, you end up at (1,1). If you go Down then Right, you also end up at (1,1). The brute force tree computes the paths from (1,1) to the end twice. DP solves this by saving the work.

The pattern ​

Same question as every DP: how did I get here?

You can only arrive at a cell from the left or from above. Those two routes are disjoint and cover everything, so:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

Counting, so the operator is + — this is 4.23.1 Climbing Stairs in two dimensions.

The base cases are the first row and the first column, which all hold 1: there is exactly one way to reach any cell in the top row (keep going right) and any cell in the left column (keep going down).

A picture to hold in mind. Imagine you're collecting water in a grid of buckets. Water can only flow into a bucket from the one directly above it, or the one directly to its left. If you want to know how much water ends up in a specific bucket, you just add together the water spilling in from the top bucket and the water spilling in from the left bucket. The "aha moment" is realizing you don't need to trace every drop from the source; you only care about your immediate neighbors.

The fill order ​

This is what 2-D DP is really about, so we state it clearly even on an easy problem.

dp[r][c] reads dp[r-1][c] and dp[r][c-1] — both a smaller row or a smaller column. So filling top to bottom, left to right guarantees every cell it needs is already there.

Always check this before writing the loops. List what the recurrence reads, and choose an order where those cells come first. Half of all 2-D DP bugs are reading a cell that has not been filled.

The solution ​

python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n                        # (1) the top row: one way to each cell

        for _ in range(1, m):  # (2)
            for c in range(1, n):  # (3)
                row[c] += row[c - 1]         # (4) from above (old) + from the left (new)

        return row[-1]  # (5)
ts
function uniquePaths(m: number, n: number): number {
  const row = new Array(n).fill(1);  // (1)

  for (let r = 1; r < m; r++) {  // (2)
    for (let c = 1; c < n; c++) {  // (3)
      row[c] += row[c - 1];  // (4)
    }
  }

  return row[n - 1];  // (5)
}

Line by line ​

(1) Initialize the array. row = [1] * n creates our 1D DP table. Since we only ever need the "current" row and the "previous" row, we start by pretending this is row 0 (the top edge), where every cell has exactly 1 path to it.

(2) Iterate through rows. for _ in range(1, m): starts at row 1 and goes down to the bottom.

(3) Iterate through columns. for c in range(1, n): starts at column 1 (since column 0 is always 1 path straight down).

(4) The Transition. row[c] += row[c - 1]. On the right side of the +=, row[c] is the value from the row above (because we haven't overwritten it yet), and row[c-1] is the value from the left (because we just updated it in the previous iteration of the loop).

(5) Return result. row[-1] gives us the last element of the row, which corresponds to the bottom-right corner.

row[c] += row[c - 1] is the rolled-array version. We unpack it here, because the same line appears throughout this chapter.

At the moment the line runs:

  • row[c] still holds the value from the previous row — that is the "from above" term.
  • row[c - 1] has already been updated in this row — that is the "from the left" term.

So one array does the job of two, and the update reads exactly the two cells the recurrence needs. This only works because the loop goes left to right; reversing it would read the wrong row[c-1].

The full-table version is easier to see first:

python
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
    for c in range(1, n):
        dp[r][c] = dp[r-1][c] + dp[r][c-1]
return dp[m-1][n-1]

O(mn) time, O(mn) space. Write this, then collapse to the single row and say why the collapse is legal.

Hand Trace ​

Let's trace m = 3, n = 3.

  1. Start: row = [1, 1, 1] (Represents Row 0).
  2. Row 1:
    • c = 1: row[1] += row[0] → 1 + 1 = 2. row becomes [1, 2, 1].
    • c = 2: row[2] += row[1] → 1 + 2 = 3. row becomes [1, 2, 3].
  3. Row 2:
    • c = 1: row[1] += row[0] → 2 + 1 = 3. row becomes [1, 3, 3].
    • c = 2: row[2] += row[1] → 3 + 3 = 6. row becomes [1, 3, 6].

Final array is [1, 3, 6]. The answer is row[-1] = 6.

Complexity Derivation ​

  • Time Complexity: O(m \times n). We have two nested loops. The outer loop runs m-1 times, and the inner loop runs n-1 times. Inside the inner loop, we do a single O(1) addition. Therefore, we do a constant amount of work for each of the m \times n cells in the grid.
  • Space Complexity: O(n). We only allocate a single 1D array of size n to store the previous row's results. (If we used the 2D matrix approach, space would be O(m \times n)).

Edge cases ​

  • 1D Grid (m = 1 or n = 1): The robot can only move in a straight line. The nested loops won't even execute, and it will just return the initialized 1. This correctly matches reality.

The maths answer ​

You need exactly m − 1 downs and n − 1 rights, in some order, for a total of m + n − 2 moves. Choosing which of them are downs determines the path entirely:

\binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!\,(n-1)!}

O(\min(m,n)) time and O(1) space, computing the binomial coefficient iteratively to avoid huge factorials.

Mention it — it is the fastest answer and shows you looked at the structure rather than reaching for a table. Then note the catch: it only works because the grid is empty. Add a single obstacle and the combinatorics collapses while the DP needs one extra line.

Where this goes next ​

  • Unique Paths II — some cells are blocked. Set dp[r][c] = 0 for an obstacle, since no path can pass through it. One line, and the maths solution is gone.
  • Minimum Path Sum — the cheapest route rather than the count. + becomes min, and you add the cell's own cost.
  • Unique Paths III — visit every empty cell exactly once. That is Hamiltonian, so it is backtracking, not DP. A good reminder that a similar-sounding problem can be in a completely different complexity class.
  • Dungeon Game — the same grid filled backwards from the destination, because the constraint is about surviving the rest of the journey rather than what happened so far.

What the interviewer will push on ​

"Derive the recurrence." Arrive from the left or from above; disjoint and complete.

"What are the base cases?" The first row and first column, all 1.

"Why does the loop go in that order?" Every cell reads a smaller row and a smaller column.

"Can you use O(n) space?" One row, and explain what row[c] and row[c-1] hold at the moment of the update.

"Is there a closed form?" The binomial coefficient — and it stops working the moment obstacles appear.

"How would you handle a grid so large that the number of paths exceeds a 64-bit integer?" You would need to use a BigInt library (or Python's built-in arbitrary-precision integers). Alternatively, if they just want the answer modulo 10^9 + 7 (a common competitive programming constraint), you would simply apply % (10**9 + 7) at every addition step: row[c] = (row[c] + row[c-1]) % MOD.

One thing to volunteer: state the fill order and why before writing the loops. On this problem it is easy; on 4.24.10 Burst Balloons it is the entire difficulty, and building the habit here is what makes that one manageable.

Next: 4.24.2 Longest Common Subsequence — the grid that compares two strings, and the template for six more problems.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet