213. House Robber II

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (circular array reduction)
Difficulty: Medium
Companies: Google, Amazon, Bloomberg, Microsoft, Apple
Frequency: High
LeetCode: 213

Problem (one-liner)

Same as House Robber, but houses are arranged in a circle: first and last houses are adjacent; still no two adjacent robberies. Input: nums circular. Output: max sum.

Recognition Cues

“Circle” / “first house is neighbor of last”
Otherwise identical to linear robber
Reduce to two linear subproblems

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 — try subsets respecting circular adjacency — exponential.
Better — DP on broken circle — run linear robber twice on ranges [0..n-2] and [1..n-1].
Optimal — O(n) time / O(1) space per range — take max of two linear passes. <- pick this in interview.

Optimal Solution

Go

package main

func robLinear(nums []int, start int, endExclusive int) int {
	if start >= endExclusive {
		return 0
	}
	if endExclusive-start == 1 {
		return nums[start]
	}
	previousPrevious := nums[start]
	previous := nums[start]
	if nums[start+1] > nums[start] {
		previous = nums[start+1]
	}
	for index := start + 2; index < endExclusive; index++ {
		take := previousPrevious + nums[index]
		skip := previous
		next := skip
		if take > skip {
			next = take
		}
		previousPrevious = previous
		previous = next
	}
	return previous
}

func robTable(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	if length == 1 {
		return nums[0]
	}
	excludingLast := robLinear(nums, 0, length-1)
	excludingFirst := robLinear(nums, 1, length)
	if excludingLast > excludingFirst {
		return excludingLast
	}
	return excludingFirst
}

func rob(nums []int) int {
	return robTable(nums)
}

JavaScript

function robLinear(nums, start, endExclusive) {
	if (start >= endExclusive) return 0;
	if (endExclusive - start === 1) return nums[start];
	let previousPrevious = nums[start];
	let previous = Math.max(nums[start], nums[start + 1]);
	for (let index = start + 2; index < endExclusive; index++) {
		const next = Math.max(previous, previousPrevious + nums[index]);
		previousPrevious = previous;
		previous = next;
	}
	return previous;
}

function rob(nums) {
	const length = nums.length;
	if (length === 0) return 0;
	if (length === 1) return nums[0];
	return Math.max(
		robLinear(nums, 0, length - 1),
		robLinear(nums, 1, length)
	);
}