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.

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]

Diagram

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

Loading diagram…

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];
}