Coding problem · Medium · Dynamic Programming

House Robber

Medium Algorithms & data structures Seen at Amazon, Google, Cisco

Houses along a street hold amounts nums[i]. Adjacent houses have connected alarms, so you can't rob two neighbours. Return the maximum amount you can rob.

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob houses 0 and 2.

Example 2

Input: nums = [2,7,9,3,1]
Output: 12

Hints

Hint 1

At each house: skip it (keep the best so far) or rob it (best up to two houses back + this one).

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

best(i) = max(best(i-1), best(i-2) + nums[i]). Only the previous two values are needed, so roll two variables through the array.

Reference solution

function rob(nums) {
  let prev = 0, cur = 0;
  for (const x of nums) [prev, cur] = [cur, Math.max(cur, prev + x)];
  return cur;
}

function rob(nums: number[]): number {
  let prev = 0, cur = 0;
  for (const x of nums) [prev, cur] = [cur, Math.max(cur, prev + x)];
  return cur;
}

def rob(nums: list[int]) -> int:
    prev = cur = 0
    for x in nums:
        prev, cur = cur, max(cur, prev + x)
    return cur

<?php

function rob(array $nums): int
{
    $prev = $cur = 0;
    foreach ($nums as $x) {
        [$prev, $cur] = [$cur, max($cur, $prev + $x)];
    }
    return $cur;
}

class Solution {
    public int rob(int[] nums) {
        int prev = 0, cur = 0;
        for (int x : nums) { int next = Math.max(cur, prev + x); prev = cur; cur = next; }
        return cur;
    }
}

Follow-up questions

Houses in a circle (House Robber II): run twice, excluding the first or the last house.