Start learning free

LESSON 444 OF 535 · DYNAMIC PROGRAMMING

House Robber II in C++: Circular Street, O(n) Time and O(1) Space

Practice O(n) Read the full explanation

You are a robber planning to rob houses that stand in a circle: house 0 comes after the last house, so the first house and the last house are neighbors. Each house has some money stashed, given in a vector nums: house i holds nums[i].

Neighboring houses share a security system: if two adjacent houses are robbed on the same night, the police are alerted. Return the maximum amount of money you can rob tonight without alerting the police.

This is House Robber with one change: the street is now a circle, so the first and the last house can't both be robbed.

Example 1:

Input: nums = [2, 3, 2]
Output: 3
Explanation: House 0 and house 2 both hold 2, but they are neighbors in the circle, so they can't both be robbed. Rob house 1 (money 3).

Example 2:

Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (money 1) and house 2 (money 3): 1 + 3 = 4.

Example 3:

Input: nums = [400, 0, 0, 400, 0, 0, 400]
Output: 800
Explanation: On a street with two ends, houses 0, 3 and 6 would give 1200. In the circle, house 6 is next to house 0, so only two of those three houses can be robbed, for example houses 0 and 3: 400 + 400 = 800.

Constraints:

  • 1 <= nums.size() <= 100
  • 0 <= nums[i] <= 1000

Note:

Your algorithm should run in O(n) time, where n is the number of houses.

STEP 1 OF 12
    Ctrl + Enter to check

    C++ · DYNAMIC PROGRAMMING

    House Robber Ii in C++, explained

    Problem overview

    The method rob receives a vector nums, where nums[i] is the money in house i. The houses stand in a circle, so house 0 comes right after the last house and the two are neighbours. Robbing two neighbouring houses on the same night alerts the police. The method returns the largest amount that can be robbed without that.

    This is the classic House Robber with one change: on a street with two ends, the first and last house are not neighbours. In a circle they are, so they can't both be robbed.

    For nums = [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each, but they are neighbours in the circle, so robbing both is not allowed. Robbing house 1 gives 3. For nums = [1, 2, 3, 1] the answer is 4, from houses 0 and 2: 1 + 3.

    Approach: break the circle into two streets

    The circle has one extra rule: the first and the last house are never both robbed. So every valid plan leaves out the first house or the last house (or both). That suggests two cases:

    • Leave out the last house. The houses 0 to n - 2 form a street with two ends, which is the ordinary House Robber.
    • Leave out the first house. The houses 1 to n - 1 form another ordinary street.

    The answer is the larger result of the two cases. A plan that robs neither end appears in both cases, which is harmless, because only the best total matters. No valid plan is missed: whichever end it skips, one of the two runs includes it.

    Each street is solved with the usual two running totals. Looking at one house at a time, the best total so far is either the best without this house (skip it) or the money in this house plus the best up to two houses back (rob it, which forces the previous house to stay untouched). Only the last two best totals are needed, so the memory stays constant.

    For nums = [400, 0, 0, 400, 0, 0, 400], a straight street would let you rob houses 0, 3 and 6 for 1200. In the circle, houses 6 and 0 are neighbours. The run over houses 0 to 5 gives 800, the run over houses 1 to 6 gives 800, and the answer is 800.

    Step by step

    1. Store the number of houses in int n = nums.size().
    2. Handle one house. If n == 1, return nums[0]. A single house has no neighbour, so it is robbed. The two cases below each drop a house, and with one house nothing would be left.
    3. Leave out the last house. Store robRange(nums, 0, n - 2) in withoutLast. At this point the helper is assumed to exist: it solves House Robber for the houses from start to end. Writing it afterwards keeps rob short.
    4. Leave out the first house. Store robRange(nums, 1, n - 1) in withoutFirst.
    5. Return the larger one with max(withoutLast, withoutFirst).
    6. Declare the helper. robRange takes vector<int>& nums and two ints, start and end, and returns an int.
    7. Create prev, starting at 0. It is the best total from the houses of the range up to two houses before the current one. Before the first house of the range, nothing has been robbed.
    8. Create curr, also starting at 0. It is the best total up to the house just before the current one.
    9. Loop over the range with i from start while i <= end. The comparison is <=, because house end belongs to the range.
    10. Compute the best total up to house i: int best = max(curr, prev + nums[i]). Either skip the house and keep curr, or rob it and add its money to prev.
    11. Shift both totals right: prev = curr; and then curr = best;. The order matters: changing curr first would lose the value prev needs.
    12. Return curr after the loop. It is the best total for the whole range.

    The solution in C++

    class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        int withoutLast = robRange(nums, 0, n - 2);
        int withoutFirst = robRange(nums, 1, n - 1);
        return max(withoutLast, withoutFirst);
    }

    int robRange(vector<int>& nums, int start, int end) {
        int prev = 0;
        int curr = 0;
        for (int i = start; i <= end; i++) {
            int best = max(curr, prev + nums[i]);
            prev = curr;
            curr = best;
        }
        return curr;
    }
};

    The two runs on the examples give these results, as robRange over houses 0 to n - 2 and then over houses 1 to n - 1:

    [2, 3, 2]                      3 and 3 -> 3
[1, 2, 3, 1]                   4 and 3 -> 4
[400, 0, 0, 400, 0, 0, 400]    800 and 800 -> 800

    The C++ details worth a closer look:

    • Passing by reference. vector<int>& nums hands the helper the vector itself. Calling it twice copies nothing.
    • Ranges are inclusive. robRange(nums, 0, n - 2) includes both house 0 and house n - 2. That is why the loop condition is i <= end.
    • Member functions can call each other in any order. Inside a class body, rob may call robRange even though it is written below.
    • A signed n. nums.size() is unsigned, but n is an int, so n - 2 is an ordinary integer. With n of 2, the first run covers the range 0 to 0 and the second covers 1 to 1. If n - 2 were computed on the unsigned size with an empty vector, it would wrap around, but the constraints guarantee at least one house.
    • max needs matching types. Both arguments of max here are int. Mixing int and long long in one call would not compile without a cast.

    Complexity

    Time: O(n). Each call of robRange goes through at most n - 1 houses with constant work per house. Two calls visit each house at most twice.

    Space: O(1). The code keeps a few integers (prev, curr, best and the two results), whatever the number of houses.

    Edge cases and common mistakes

    • One house. [5] returns 5. Without the n == 1 check, both calls would use an empty or reversed range, and the answer would be 0.
    • Two houses. They are neighbours in both directions, so only one can be robbed. [2, 7] returns 7: the first run covers house 0 alone and the second covers house 1 alone.
    • Three equal houses. [1, 1, 1] returns 1. On a straight street the answer would be 2, but houses 0 and 2 are neighbours here.
    • Zeros. [0, 0] returns 0. The values may be 0, so a plan that robs nothing is valid.
    • Ignoring the circle. Running the plain House Robber over all houses answers 1200 for the third example. The correct answer is 800.
    • Dropping the wrong houses. Both ranges must differ by exactly one end. Using 0 .. n - 2 twice, or 0 .. n - 1 in one of the runs, leaves the circle unbroken or loses some plans.
    • Updating in the wrong order. Writing curr = best before prev = curr sets prev to the new total, so a house could be added to the total that already includes its neighbour.

    Testing

    • nums = [2, 3, 2] gives 3.
    • nums = [1, 2, 3, 1] gives 4.
    • nums = [400, 0, 0, 400, 0, 0, 400] gives 800.
    • nums = [5] gives 5.
    • nums = [2, 7] gives 7.
    • nums = [1, 1, 1] gives 1.
    • nums = [4, 1, 1, 4] gives 5.
    • nums = [0, 0] gives 0.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free