Given n houses in a line with money in each, find the maximum amount a robber can steal, without stealing from two adjacent houses.
MediumUnlock detailed company stats for this questionUpgrade
You are given an array representing the value in the houses e.g. [100, 20, 40, 70, 80]. Return 100 + 40 + 80 = 220
You're planning to rob houses along a street. House i holds nums[i] in cash, and neighboring houses share an alarm system: robbing two adjacent houses on the same night alerts the police.
Return the most money you can take without robbing two adjacent houses.
Example 1
Input: nums = [1, 2, 3, 1] Output: 4
Rob house 0 (1) and house 2 (3).
Example 2
Input: nums = [2, 7, 9, 3, 1] Output: 12
Rob houses 0, 2 and 4: 2 + 9 + 1 = 12.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 400
Approach
Trying every set of non-adjacent houses takes exponential time, but the choices overlap. The best haul from the first i houses doesn't depend on anything you do later. So at each house, compare two options: rob it, which adds its cash to the best haul from two houses back, or skip it, which keeps the best haul from one house back. Only the last two results ever matter, so you can keep them in two variables.
Steps
- Set
prev2 = 0andprev1 = 0, the best totals up to two houses back and one house back. - For each house value
x, computecur = max(prev1, prev2 + x). - Shift the window:
prev2becomesprev1, andprev1becomescur. - Return
prev1.
Complexity
- Time:
O(n). One pass over the houses. - Space:
O(1). Two running totals.
Common mistakes
- Robbing every other house, starting from house 0 or house 1. The best plan can skip two houses in a row: for
[2, 1, 1, 2], robbing the first and last houses gives4. - Overwriting
prev1before copying it intoprev2. Update both from the old values at the same time.
Interview experiences
2 sharedRelated courses

Course

Course






