198. House Robber

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (take-or-skip on a line)
Difficulty: Medium
Companies: Google, Amazon, Meta, Bloomberg, Microsoft
Frequency: Very High
LeetCode: 198

Problem (one-liner)

Given non-negative money per house in a line, you cannot rob two adjacent houses. Maximize the total money robbed. Input: nums array. Output: maximum sum.

Recognition Cues

“Cannot rob two adjacent”
“Maximize” on a 1D array with local conflict
Classic “include/exclude” at each index

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 — O(2^n) — every subset without adjacent.
Better — top-down DP — O(n) time / O(n) space.
Optimal — two-state rolling max — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func robTable(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	if length == 1 {
		return nums[0]
	}
	dp := make([]int, length)
	dp[0] = nums[0]
	if nums[1] > nums[0] {
		dp[1] = nums[1]
	} else {
		dp[1] = nums[0]
	}
	for index := 2; index < length; index++ {
		skip := dp[index-1]
		take := dp[index-2] + nums[index]
		if take > skip {
			dp[index] = take
		} else {
			dp[index] = skip
		}
	}
	return dp[length-1]
}

func rob(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	if length == 1 {
		return nums[0]
	}
	previousPrevious := nums[0]
	previous := nums[0]
	if nums[1] > nums[0] {
		previous = nums[1]
	}
	for index := 2; index < length; index++ {
		take := previousPrevious + nums[index]
		skip := previous
		next := skip
		if take > skip {
			next = take
		}
		previousPrevious = previous
		previous = next
	}
	return previous
}

JavaScript

function robTable(nums) {
	const length = nums.length;
	if (length === 0) return 0;
	if (length === 1) return nums[0];
	const dp = new Array(length);
	dp[0] = nums[0];
	dp[1] = Math.max(nums[0], nums[1]);
	for (let index = 2; index < length; index++) {
		dp[index] = Math.max(dp[index - 1], dp[index - 2] + nums[index]);
	}
	return dp[length - 1];
}

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