63. Unique Paths II

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (grid with obstacles)
Difficulty: Medium
Companies: Amazon, Google, Bloomberg, Microsoft, Oracle
Frequency: High
LeetCode: 63

Problem (one-liner)

Same movement as Unique Paths, but grid[row][col] == 1 marks an obstacle (cannot enter). Count paths from top-left to bottom-right. Input: obstacleGrid. Output: path count.

Recognition Cues

“Obstacle” / value 1 blocks cell
First row/column can be blocked → cascade zeros
Same recurrence when cell not blocked

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

Brute force — DFS — exponential.
Better — full 2D DP — O(m*n) time / O(m*n) space.
Optimal — one-row rolling with obstacle checks — O(m*n) time / O(n) space. <- pick this in interview.

Optimal Solution

Go

package main

func uniquePathsWithObstaclesTable(obstacleGrid [][]int) int {
	rows := len(obstacleGrid)
	if rows == 0 {
		return 0
	}
	cols := len(obstacleGrid[0])
	table := make([][]int, rows)
	for row := range table {
		table[row] = make([]int, cols)
	}
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	table[0][0] = 1
	for col := 1; col < cols; col++ {
		if obstacleGrid[0][col] == 1 {
			table[0][col] = 0
		} else {
			table[0][col] = table[0][col-1]
		}
	}
	for row := 1; row < rows; row++ {
		if obstacleGrid[row][0] == 1 {
			table[row][0] = 0
		} else {
			table[row][0] = table[row-1][0]
		}
		for col := 1; col < cols; col++ {
			if obstacleGrid[row][col] == 1 {
				table[row][col] = 0
			} else {
				table[row][col] = table[row-1][col] + table[row][col-1]
			}
		}
	}
	return table[rows-1][cols-1]
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	rows := len(obstacleGrid)
	if rows == 0 {
		return 0
	}
	cols := len(obstacleGrid[0])
	row := make([]int, cols)
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	row[0] = 1
	for col := 1; col < cols; col++ {
		if obstacleGrid[0][col] == 1 {
			row[col] = 0
		} else {
			row[col] = row[col-1]
		}
	}
	for iterRow := 1; iterRow < rows; iterRow++ {
		if obstacleGrid[iterRow][0] == 1 {
			row[0] = 0
		}
		for col := 1; col < cols; col++ {
			if obstacleGrid[iterRow][col] == 1 {
				row[col] = 0
			} else {
				row[col] += row[col-1]
			}
		}
	}
	return row[cols-1]
}

JavaScript

function uniquePathsWithObstacles(obstacleGrid) {
	const rows = obstacleGrid.length;
	if (rows === 0) return 0;
	const cols = obstacleGrid[0].length;
	if (obstacleGrid[0][0] === 1) return 0;
	const row = new Array(cols).fill(0);
	row[0] = 1;
	for (let col = 1; col < cols; col++) {
		row[col] = obstacleGrid[0][col] === 1 ? 0 : row[col - 1];
	}
	for (let iterRow = 1; iterRow < rows; iterRow++) {
		if (obstacleGrid[iterRow][0] === 1) {
			row[0] = 0;
		}
		for (let col = 1; col < cols; col++) {
			if (obstacleGrid[iterRow][col] === 1) {
				row[col] = 0;
			} else {
				row[col] += row[col - 1];
			}
		}
	}
	return row[cols - 1];
}