54. House Robber

MediumArray Dynamic Programming

A burglar is walking down a street of houses. nums[i] is the amount of cash hidden in house i. The houses share a security system: if cash is taken from two neighbouring houses on the same night, the alarm goes off.

Return the largest total the burglar can collect without ever taking from two adjacent houses.

Example 1

Input: nums = [3,1,4,1,5]
Output: 12

Explanation: Take houses 0, 2 and 4: 3 + 4 + 5 = 12.

Example 2

Input: nums = [2,9,4,1]
Output: 10

Explanation: Take houses 1 and 3: 9 + 1 = 10. The every-other-house pattern starting at house 0 only gives 2 + 4 = 6.

Example 3

Input: nums = [5,1,1,5]
Output: 10

Explanation: Skipping two houses in a row is allowed: take houses 0 and 3.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 400

Follow-up: What changes if the houses stand in a circle, so the first and last house are also neighbours?

💡 Hint 1

Greedy choices (always take the biggest, or always take every other house) fail. Try [2,9,4,1] and [5,1,1,5].

💡 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