62. Unique Paths

At a Glance

• Topic: dp-2d
• Pattern: Dynamic Programming (grid paths)
• Difficulty: Medium
• Companies: Google, Amazon, Bloomberg, Microsoft, Adobe
• Frequency: Very High
• LeetCode: 62

Problem (one-liner)

Robot starts top-left of an m x n grid, moves only right or down. Count paths to bottom-right. Input: m, n. Output: number of distinct paths.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Only right and down”
• “How many unique paths” on a grid
• Recurrence: ways[row][col] = ways[row-1][col] + ways[row][col-1]

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Math — binomial coefficient (m+n-2 choose m-1) — watch overflow / combinatorics.
• Better — full 2D DP table — O(m*n) time / O(m*n) space.
• Optimal — single row rolling — O(m*n) time / O(min(m,n)) space. <- pick this in interview.

Optimal Solution

Go

package main

func uniquePathsTable(m int, n int) int {
	table := make([][]int, m)
	for row := range table {
		table[row] = make([]int, n)
	}
	for col := 0; col < n; col++ {
		table[0][col] = 1
	}
	for row := 0; row < m; row++ {
		table[row][0] = 1
	}
	for row := 1; row < m; row++ {
		for col := 1; col < n; col++ {
			table[row][col] = table[row-1][col] + table[row][col-1]
		}
	}
	return table[m-1][n-1]
}

func uniquePaths(m int, n int) int {
	row := make([]int, n)
	for col := range row {
		row[col] = 1
	}
	for iterRow := 1; iterRow < m; iterRow++ {
		for col := 1; col < n; col++ {
			row[col] += row[col-1]
		}
	}
	return row[n-1]
}

JavaScript

function uniquePathsTable(m, n) {
	const table = Array.from({ length: m }, () => new Array(n).fill(0));
	for (let col = 0; col < n; col++) {
		table[0][col] = 1;
	}
	for (let row = 0; row < m; row++) {
		table[row][0] = 1;
	}
	for (let row = 1; row < m; row++) {
		for (let col = 1; col < n; col++) {
			table[row][col] = table[row - 1][col] + table[row][col - 1];
		}
	}
	return table[m - 1][n - 1];
}

function uniquePaths(m, n) {
	const row = new Array(n).fill(1);
	for (let iterRow = 1; iterRow < m; iterRow++) {
		for (let col = 1; col < n; col++) {
			row[col] += row[col - 1];
		}
	}
	return row[n - 1];
}

Walkthrough

m = 3, n = 3 table:

Invariant: each cell counts paths to it from start using only right/down.

Edge Cases

• m or n equals 1 → exactly one path
• Large grids → use big integers if language requires

Pitfalls

• Confusing m rows vs n columns in loops
• Using floating combinatorics without exact integer arithmetic

Similar Problems

• 63. Unique Paths II — obstacles block cells.
• 1143. Longest Common Subsequence — different grid meaning, same table technique.
• 097. Interleaving String — 2D feasibility on strings.

Variants

• Minimum cost path with obstacles → combine with weights.

Mind-Map Tags

#grid-dp #combinatorics #path-count #rolling-row #medium