#198 House Robber
frequently reported atInfosysAmazonByteDance / TikTokAirbnbWalmartMicrosoft
the problem
In plain words
Houses in a row hold nums[i] money. You can't rob two adjacent houses. What is the most money you can rob?
in nums = [1,2,3,1]
out 4
Rob houses 0 and 2: 1 + 3.
in nums = [2,7,9,3,1]
out 12
Rob 2 + 9 + 1.
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
At each house there are only two choices: rob it (then add the best from two houses back) or skip it (keep the best from one house back).
solutions
From brute force to optimal
best(i) = max(nums[i] + best(i+2), best(i+1)).
- Base: past the end → 0.
- Try both choices, return the max.
Two branches per house (more precisely ~1.618ⁿ, like Fibonacci).
Recursion depth.
class Solution { public int rob(int[] nums) { return best(nums, 0); } /** Best loot from houses i..n-1. */ private int best(int[] nums, int i) { if (i >= nums.length) return 0; int take = nums[i] + best(nums, i + 2); // rob i, so i+1 is off-limits int skip = best(nums, i + 1); // leave i alone return Math.max(take, skip); }}Cache best(i); there are only n different i values.
- memo filled with −1 (loot can be 0, so 0 can't mean unknown).
- Check, compute, store.
n states × O(1).
Memo + stack.
class Solution { public int rob(int[] nums) { int[] memo = new int[nums.length]; Arrays.fill(memo, -1); // -1 = not computed (loot is never negative) return best(nums, 0, memo); } private int best(int[] nums, int i, int[] memo) { if (i >= nums.length) return 0; if (memo[i] != -1) return memo[i]; return memo[i] = Math.max(nums[i] + best(nums, i + 2, memo), best(nums, i + 1, memo)); }}dp[i] = best loot from the first i houses.
- dp[0] = 0, dp[1] = nums[0].
- dp[i] = max(dp[i−1], dp[i−2] + nums[i−1]).
One pass.
The table.
class Solution { public int rob(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; // dp[i] = best loot from the first i houses dp[1] = nums[0]; for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; }}Keep prev1 (best so far) and prev2 (best one house earlier).
- For each x: cur = max(prev2 + x, prev1).
- Shift: prev2 = prev1, prev1 = cur.
One pass.
Two ints.
class Solution { public int rob(int[] nums) { int prev2 = 0, prev1 = 0; // best loot up to two houses back / one house back for (int x : nums) { int take = prev2 + x; // rob this house int skip = prev1; // do not rob it int cur = Math.max(take, skip); prev2 = prev1; prev1 = cur; } return prev1; }}Take or skip, house by house
in the room
How to say it in the interview
talk track
- "Greedy (take the biggest, or all even indices) fails: [2,1,1,2] → best is 2 + 2 = 4, not either parity."
- State the recurrence, then climb the ladder to O(1) space.
traps
- Robbing all even or all odd houses is not optimal ([2,1,1,2]).
- Using 0 as "unknown" in the memo when the loot can be 0.
what they ask next
Follow-ups
Houses in a circle (LC 213)?
Run the line version twice: without the last house and without the first. See House Robber II.
Houses on a binary tree (LC 337)?
Tree DP: each node returns a pair (best if robbed, best if not).
before you submit
Edge cases to test
- One house → its money.
- [2,1,1,2] → 4: neither "all even" nor "all odd" houses.
- All zeros → 0, so 0 can't mean "not computed" in a memo.
practise next
Similar problems
- #213House Robber IIMediumin Dynamic Programming
- #746Min Cost Climbing StairsEasyin Dynamic Programming
- #70Climbing StairsEasyin Dynamic Programming