Solutions

1. Recursion

O(2ⁿ) time | O(n) space

Intuition

The largest amount we can make starting from the first house is the greater of two:

• The first house amount plus the largest amount we can make starting from the third house (skipping the second house).
• The largest amount we can make starting from the second house (skipping the first house).

We can recursively apply the same logic to calculate the largest amount starting from any house until we reach the last one.

Algorithm

1. Create a robAt function taking the array and a start index.
   • Return 0 when start is past the last house.
   • Otherwise calculate robAt from start + 2 and add the value at start to it, calculate robAt from start + 1, and return the greater of the two.
2. Return robAt called with the array and a start of 0.

Code

def rob(nums: list[int]) -> int:
    return robAt(nums, 0)


def robAt(nums: list[int], start: int) -> int:
    if start >= len(nums):
        return 0
    return max(nums[start] + robAt(nums, start + 2), robAt(nums, start + 1))

/**
 * @param {number[]} nums
 * @returns {number}
 */
var rob = function (nums) {
  return robAt(nums, 0)
}

function robAt(nums, start) {
  if (start >= nums.length) return 0
  return Math.max(nums[start] + robAt(nums, start + 2), robAt(nums, start + 1))
}

class Solution {
    public int rob(int[] nums) {
        return robAt(nums, 0);
    }

    private int robAt(int[] nums, int start) {
        if (start >= nums.length) return 0;
        return Math.max(nums[start] + robAt(nums, start + 2), robAt(nums, start + 1));
    }
}

2. Dynamic Programming, Top Down

O(n) time | O(n) space

Intuition

The largest amount we can make starting from the first house is the greater of two:

• The first house amount plus the largest amount we can make starting from the third house (skipping the second house).
• The largest amount we can make starting from the second house (skipping the first house).

We can recursively apply the same logic to calculate the largest amount starting from any house until we reach the last one.

To avoid repeating the same calls, we can store the largest amounts we can make starting from each house in a hash map.

Algorithm

1. Create a robAt function taking the array, a start index and a hash map.
   • Return 0 when start is past the last house.
   • Return the value from the hash map for start when it is there.
   • Otherwise calculate robAt from start + 2 and add the value at start to it, calculate robAt from start + 1 and get the greater of the two.
   • Add the result to the hash map against start and return it.
2. Return robAt called with the array, a start of 0 and an empty hash map.

Code

def rob(nums: list[int]) -> int:
    return robAt(nums, 0, {})


def robAt(nums: list[int], start: int, known: dict[int, int]) -> int:
    if start >= len(nums):
        return 0
    if start not in known:
        known[start] = max(nums[start] + robAt(nums, start + 2, known),
                           robAt(nums, start + 1, known))
    return known[start]

/**
 * @param {number[]} nums
 * @returns {number}
 */
var rob = function (nums) {
  return robAt(nums, 0, new Map())
}

function robAt(nums, start, known) {
  if (start >= nums.length) return 0
  if (!known.has(start)) {
    known.set(start, Math.max(nums[start] + robAt(nums, start + 2, known), robAt(nums, start + 1, known)))
  }
  return known.get(start)
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int rob(int[] nums) {
        return robAt(nums, 0, new HashMap<>());
    }

    private int robAt(int[] nums, int start, Map<Integer, Integer> known) {
        if (start >= nums.length) return 0;
        Integer stored = known.get(start);
        if (stored != null) return stored;
        int most = Math.max(nums[start] + robAt(nums, start + 2, known), robAt(nums, start + 1, known));
        known.put(start, most);
        return most;
    }
}

3. Dynamic Programming, Bottom Up

O(n) time | O(1) space

Intuition

The largest amount we can make starting from the first house is the greater of two:

• The first house amount plus the largest amount we can make starting from the third house (skipping the second house).
• The largest amount we can make starting from the second house (skipping the first house).

As the last house does not have houses ahead, the largest amount we can make from it is that house's money itself. Then we can calculate the largest amount from each earlier house one by one, reusing values from the calculated positions.

Algorithm

1. Create current and previous variables with initial values 0 and 0, the answers for the two places past the last house.
2. Iterate through the loop from the last house to the first house.
   • Calculate the greater of the money at this house plus previous, and current.
   • Update previous with current, and current with the greater.
3. Return current.

Code

def rob(nums: list[int]) -> int:
    current, previous = 0, 0
    for money in reversed(nums):
        current, previous = max(money + previous, current), current
    return current

/**
 * @param {number[]} nums
 * @returns {number}
 */
var rob = function (nums) {
  let current = 0
  let previous = 0
  for (let i = nums.length - 1; i >= 0; i--) {
    const most = Math.max(nums[i] + previous, current)
    previous = current
    current = most
  }
  return current
}

class Solution {
    public int rob(int[] nums) {
        int current = 0;
        int previous = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            int most = Math.max(nums[i] + previous, current);
            previous = current;
            current = most;
        }
        return current;
    }
}