House Robber

easy Coding Interview Patterns 10–15 min

NumPy allowed · plain Python earns 10 bonus points

Implement House Robber -- the classic 1-D DP problem with recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]), reducible to O(1) space with two rolling variables.

Related Skills

Task

Implement rob(nums): at each house, decide whether skipping it (carry forward the best sum so far) or robbing it (best sum from two houses back, plus this house) is larger. Roll two variables (prev2, prev1) forward instead of a full DP array.

Function Signature

rob(nums: list[int]) -> int

Examples

Example 1: Skip-Then-Rob Pattern
Input: nums = [1, 2, 3, 1]
Output: 4
Example 2: Alternating Houses Optimal
Input: nums = [2, 7, 9, 3, 1]
Output: 12

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • An empty list returns 0.
  • Must run in O(n) time and O(1) space.
Python3Saved ✓
def rob(nums: list[int]) -> int:
"""nums: list of non-negative ints (money in each house). Return the
max sum collectible without robbing two adjacent houses."""
# Your implementation here
pass

Case 1: Skip-Then-Rob Pattern
Input: nums = [1, 2, 3, 1]
Expected: 4
Case 2: Alternating Houses Optimal
Input: nums = [2, 7, 9, 3, 1]
Expected: 12