House robber: maximize loot without hitting adjacent houses
Filed under Deutsche Bank
Check for an empty list, zero values, and whether the houses form a line (not a circle).
The question
Houses stand in a line, each holding some money. A thief cannot rob two adjacent houses. Given the amounts, return the maximum total he can rob.
Constraints
- 0 <= n <= 10^5
- Amounts are non-negative integers
- Adjacent houses cannot both be robbed
Examples
- Input
- [2, 7, 9, 3, 1]
- Output
- 12
- Why
- Rob houses 1, 3 and 5: 2 + 9 + 1 = 12.
- Input
- [1, 2, 3, 1]
- Output
- 4
- Why
- Rob houses 1 and 3: 1 + 3 = 4.
Approach
Check for an empty list, zero values, and whether the houses form a line (not a circle).
Recurse: rob(i) = max(rob(i+1), nums[i] + rob(i+2)). This recomputes states and is O(2^n).
Let best[i] be the max loot from the first i houses: best[i] = max(best[i-1], best[i-2] + nums[i]). Only the last two values are needed, so use two variables.
Empty array returns 0, one house returns its value. For the circular variant, run the DP twice excluding the first and then the last house.
Solution
O(n) time, O(1) space
def rob(nums):
prev, cur = 0, 0 # best loot up to two houses ago / one house ago
for x in nums:
prev, cur = cur, max(cur, prev + x) # skip house, or rob it
return cur
Tips
- What they are testing: Turning a choice at each step (rob or skip) into a clean recurrence and then compressing to two variables.
- Common mistake: Greedily taking the larger of each adjacent pair or alternating houses, which fails on inputs like [2, 1, 1, 2].
Related Deutsche Bank questions
Collected from public candidate posts and coding forums. Updated Nov 2026.