House Robber II

The problem

This is House Robber with one change: the houses stand in a circle, so the first house and the last house are neighbors. nums[i] is the money in house i. You may never take from two neighboring houses. Return the most money you can take.

Example 1

Input: nums = [3, 1, 4, 9]

Output: 10

On a straight street, houses 0 and 3 would give 12. In a circle they are neighbors, so the best is houses 1 and 3: 1 + 9 = 10.

Example 2

Input: nums = [5]

Output: 5

A single house has no neighbor, so take it.

Example 3

Input: nums = [6, 2, 5]

Output: 6

In a circle of three, every pair of houses are neighbors. So take only the richest one.

Constraints

• 1 ≤ nums.length ≤ 100 (call it n)
• 0 ≤ nums[i] ≤ 1000

Clarifying questions

With one house, is it its own neighbor?

No. A single house can be taken.

With two houses, can we take both?

No. They are neighbors, so take the richer one.

Is anything else different from House Robber?

No. Only the first and last house now touch.

Spot the pattern

The circle adds exactly one rule: not both the first and the last house. So every allowed plan leaves out the first house, or leaves out the last one. Leaving one out turns the circle into a straight street, which House Robber already solves with dynamic programming. Breaking a circle into two straight cases is a common trick.

Solutions

Two straight streetsO(n)

Show all

There is only one approach worth showing. The plain recursion and the table from House Robber work here too, run twice, and cost the same as they did there.

Two straight streets O(n)

The idea

Solve the straight street twice with the two-number method from House Robber:

1. Houses 0 to n − 2: everything except the last house.
2. Houses 1 to n − 1: everything except the first house.

Return the bigger result. With only one house, both streets would be empty, so return that house’s money first.

Why it is correct: the best plan in the circle never takes both the first and the last house. So it is an allowed plan on at least one of the two streets, and that street’s best is at least as big. Every plan on either street is also allowed in the circle, so neither result can be too big.

Walkthrough

1. if len(nums) == 1: return nums[0]
2. without_last = line(houses 0 .. len(nums) - 2)
3. without_first = line(houses 1 .. len(nums) - 1); return max(without_last, without_first)
4. def line(houses):
5. for money in houses:
6. two_back, one_back = one_back, max(one_back, money + two_back)
7. return one_back

The houses stand in a circle, so house 0 and house 3 are neighbors too. At most one of them can be taken.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two straight streets: the first and last house cannot both be taken, so
    // solve the street without the last house and the street without the first. O(n) time, O(1) space.
    public int rob(int[] nums) {
        // One house has no neighbor at all.
        if (nums.length == 1) return nums[0];
        return Math.max(line(nums, 0, nums.length - 2), line(nums, 1, nums.length - 1));
    }

    private int line(int[] nums, int start, int end) {
        int twoBack = 0, oneBack = 0;
        for (int i = start; i <= end; i++) {
            // Skip this house, or take it on top of the best from two houses back.
            int bestHere = Math.max(oneBack, nums[i] + twoBack);
            twoBack = oneBack;
            oneBack = bestHere;
        }
        return oneBack;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each street is one loop. A run does one addition, one max and two moves, a fixed job, so each run of the loop counts as 1 step.

   1. if len(nums) == 1: return nums[0]
   2. without_last = line(houses 0 .. len(nums) - 2)
   3. without_first = line(houses 1 .. len(nums) - 1); return max(without_last, without_first)
   4. def line(houses):
   5. for money in houses:
   6. two_back, one_back = one_back, max(one_back, money + two_back)
   7. return one_back

2. 2 Count the runs on Example 1

   Each street has 3 of the 4 houses.

   3 + 3 = 6 runs.

   	without the last	without the first
   loop runs	3	3

   total

   3 + 3 = 6 runs

3. 3 Write the count for any n

   Each street has n − 1 houses:

   2 × (n − 1) runs

   Check it with Example 1: 2 × 3 = 6. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is n. Solving the street twice only doubles the work.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Each pass keeps two numbers, and the code walks the houses by index without copying the list. So the space is O(1).

   two_backone_back

Common mistake

Forgetting the single house

With one house, both streets are empty and both give 0, but the answer is that house’s money. Check for one house before splitting.

Tested at the limits

2,000 random circles of 1 to 10 houses with amounts 0 to 5. One, two and three houses come up often, where every house touches the others. The two straight streets gave the same answer every time as a check that tries every set of houses.

Largest inputs	Result
100 houses in a circle (the most allowed), each with up to 1,000. Two straight streets.	Under 0.001 s, and under 0.001 MB of extra memory: two numbers for each street.