062. Unique Paths

At a Glance

• Topic: Math
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 062

Problem Statement

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

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

Example 2:

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Approach & Solution Steps

• 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 JS Solution

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

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.