House Robber

MediumArray Dynamic Programming

In a stealth video game, the player's thief creeps down a street of houses, and nums[i] is the value of the loot inside house i. Neighbouring houses share an alarm system, so looting two adjacent houses in the same level sets off the alarm and ends the run.

Return the highest total loot the player can collect without ever looting two houses that stand next to each other.

Example 1

Input: nums = [6,2,3,9,1]
Output: 15

Explanation: Loot houses 0 and 3: 6 + 9 = 15.

Example 2

Input: nums = [4,10,3,1,8]
Output: 18

Explanation: Houses 1 and 4 give 10 + 8 = 18, more than the every-other-house pattern 4 + 3 + 8 = 15.

Example 3

Input: nums = [8,9,8,1]
Output: 16

Explanation: Grabbing the single richest house, 9, rules out both 8s; looting houses 0 and 2 gives 16.

Constraints

The street has between 1 and 100 houses.
Each house holds loot worth 0 to 400.

Follow-up: In a later level the houses stand around a circular plaza, so the first and last house are neighbours too. How does your solution change?

💡 Hint 1

Greedy choices (always take the richest house, or always take every other house) fail. Try [8,9,8,1] and [4,10,3,1,8].

💡 Hint 2

For house i there are two options: skip it and keep the best answer up to i - 1, or take it and add it to the best answer up to i - 2.

💡 Hint 3

Only the best totals for the last two prefixes are needed, so the extra space can be O(1).

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Let best(i) be the most cash obtainable from houses 0..i. For house i you either skip it, getting best(i - 1), or rob it, getting nums[i] + best(i - 2). Take the larger. Sweep left to right, keeping just two running values: the best totals for the prefixes ending one house back and two houses back.

Time O(n)Space O(1)

function rob(nums) {
  let prev2 = 0; // best(i - 2)
  let prev1 = 0; // best(i - 1)
  for (const cash of nums) {
    const curr = Math.max(prev1, prev2 + cash);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int cash : nums) {
            int curr = Math.max(prev1, prev2 + cash);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
function rob(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit