House Robber II

The problem

The houses of nums stand in a circle, so the first house and the last house are next to each other. nums[i] is the money in house i. A robber may take the money of any houses, as long as no two of them are next to each other. Return the largest total the robber can take. There is always at least one house, and a single house may be robbed.

What to write

function solve(nums: number[]): number

Input
nums = [2,3,2]

Output
3

Input
nums = [1,2,3,1]

Output
4

Constraints

nums is nonempty and contains nonnegative amounts.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A circle has one pair of neighbors that a straight street does not have: the first house and the last. Every other rule stays the same. A street of one house is a special case, because that house has no neighbor at all.

2. Hint 2: Ask a smaller question

   Take [1, 2, 3, 1]. Can any plan rob both house 0 and house 3? Now suppose a plan leaves house 3 alone. For the three houses that remain, does the circle still matter?

3. Hint 3: Name the pattern

   With two or more houses, no plan robs both the first and the last house. So every plan fits inside the street without its last house, or inside the street without its first. Each of those is a straight row, which House Robber solves with one-dimensional dynamic programming. Solve both rows and keep the larger total. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Inside a row, the best total after each house is the larger of two choices: the best total before this house, or this house's money plus the best total two houses back. With two or more houses, the answer for the circle is the larger of the two rows' results.

5. Hint 5: Sketch the pseudocode

   If nums has one house, return its money. row(start, end): previous = 0, current = 0; for each house from start up to end - 1: best = the larger of current and previous + its money; previous = current; current = best; the result is current. Return the larger of row(0, length - 1) and row(1, length).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

A single house is the answer by itself. Otherwise every valid plan excludes the first house or the last: solve those two straight rows as in House Robber and take the larger result.

The slow way

Try every set of houses, throw away the sets that hold two neighbors, counting the first and last house as neighbors, and keep the largest total. It is correct, but every extra house doubles the number of sets to try. Running House Robber on the circle as if it were a straight street is fast but wrong: it can rob both ends.

The insight

With two or more houses, the first and the last house are neighbors, so no plan takes both. Every plan therefore leaves the last house alone or leaves the first house alone. In either case the circle no longer matters, because the houses that remain form a straight row. Solve the row without the last house and the row without the first, and keep the better result.

Step by step

1. A single house has no neighbor, so its money is the answer. With one house, both rows below would be empty and give 0. But a house standing alone is not next to anything and can be robbed.
2. For one straight row of houses, start from a best total of 0. This helper solves House Robber for part of the street: the houses from a start position up to, but not including, an end position. Its two totals start at 0 because no house of the row has been seen yet.
3. At each house of the row, take the larger of skipping and robbing it. Skipping keeps the best total so far. Robbing adds the house's money to the best total from two houses back, since the house right before it must be left alone.
4. Keep only the two newest totals. The next house of the row needs the best total up to this house and the best up to the one before it. Anything older is never read again.
5. The newest total is the best for that row. After the last house of the row, the newest total has weighed skipping against robbing for every house in the row.
6. Leave out the last house, then the first, and keep the larger total. No plan may hold both the first and the last house, so every plan fits in one of the two rows. The larger of the two results is therefore the best plan of all.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. A single house has no neighbor, so its money is the answer
  if (nums.length === 1) return nums[0];
  // 2. For one straight row of houses, start from a best total of 0
  function rob(start, end) {
    let previous = 0;
    let current = 0;
    // 3. At each house of the row, take the larger of skipping and robbing it
    for (let i = start; i < end; i++) {
      const best = Math.max(current, previous + nums[i]);
      // 4. Keep only the two newest totals
      previous = current;
      current = best;
    }
    // 5. The newest total is the best for that row
    return current;
  }
  // 6. Leave out the last house, then the first, and keep the larger total
  return Math.max(rob(0, nums.length - 1), rob(1, nums.length));
}

function solve(nums: number[]): number {
  // 1. A single house has no neighbor, so its money is the answer
  if (nums.length === 1) return nums[0];
  // 2. For one straight row of houses, start from a best total of 0
  function rob(start: number, end: number): number {
    let previous = 0;
    let current = 0;
    // 3. At each house of the row, take the larger of skipping and robbing it
    for (let i = start; i < end; i++) {
      const best = Math.max(current, previous + nums[i]);
      // 4. Keep only the two newest totals
      previous = current;
      current = best;
    }
    // 5. The newest total is the best for that row
    return current;
  }
  // 6. Leave out the last house, then the first, and keep the larger total
  return Math.max(rob(0, nums.length - 1), rob(1, nums.length));
}

def solve(nums):
    # 1. A single house has no neighbor, so its money is the answer
    if len(nums) == 1:
        return nums[0]

    # 2. For one straight row of houses, start from a best total of 0
    def rob(start, end):
        previous = 0
        current = 0
        # 3. At each house of the row, take the larger of skipping and robbing it
        for i in range(start, end):
            best = max(current, previous + nums[i])
            # 4. Keep only the two newest totals
            previous = current
            current = best
        # 5. The newest total is the best for that row
        return current

    # 6. Leave out the last house, then the first, and keep the larger total
    return max(rob(0, len(nums) - 1), rob(1, len(nums)))

Example 2, traced

Input
nums = [1,2,3,1]

Output
4

Why it works

With two or more houses, every allowed plan leaves out the first house or the last, because the two are neighbors. A plan that leaves out the last house is a plan for the straight row without it, and the helper finds the best of those. The same holds without the first house. So the larger of the two results is the best over all plans.

Time and space

Time O(n), extra space O(1). The helper runs twice, once for each row, and each run visits its houses once, so the time is O(n) for n houses. Each run keeps only two totals, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Handle a single house first. Without that check both rows are empty, and the answer for [1] comes out as 0 instead of 1.
• Do not leave out both ends in one row. A plan may still use the first house or the last, only not both: for example 2, the row without both ends gives 3 instead of 4.
• Solve both rows. Using only the row without the last house gives 1 for [1, 2], where the answer is 2. Using only the row without the first house gives 3 for example 2, where the answer is 4.

Pattern

One-dimensional dynamic programming. Builds on House Robber.

Keep going