Start learning free

LESSON 445 OF 536 · DYNAMIC PROGRAMMING

House Robber II in Java: O(n) Dynamic Programming on a Circle

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 an array 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.length <= 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

    JAVA · DYNAMIC PROGRAMMING

    House Robber Ii in Java, explained

    Problem overview

    The method rob receives an array nums, where nums[i] is the money in house i. The houses stand in a circle, so the last house is a neighbour of house 0. Robbing two neighbouring houses on the same night alerts the police. The method returns the largest total you can rob without that.

    For nums = [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each, but they are neighbours in the circle, so only one of them can be robbed, and house 1 with its 3 is better. For nums = [1, 2, 3, 1] the answer is 4, from houses 0 and 2.

    Approach: break the circle into two streets

    On a street with two ends (the plain House Robber), the best total up to a house is either the best total up to the previous house (skip this one), or this house's money plus the best total up to two houses back (rob this one, so the previous one must stay untouched). One pass keeps just those two running totals.

    The circle adds one rule: the first and the last house can't both be robbed. So every valid plan leaves out at least one of them. That gives two cases, and each is a plain street:

    • leave out the last house and solve for houses 0 to n - 2;
    • leave out the first house and solve for houses 1 to n - 1.

    The answer is the larger of the two. A plan that robs neither end appears in both cases, which is harmless, because only the best total matters. Each case is one pass, so the whole thing takes O(n) time.

    A single house is a special case: there are no neighbours, so you rob it. Both ranges above would be empty or invalid for n == 1, and that case returns before they are used.

    Step by step

    1. Store the number of houses in n.
    2. Handle one house. If n == 1, return nums[0]. Without this, "leave out the last house" would leave nothing to look at.
    3. Leave out the last house. Call the helper robRange(nums, 0, n - 2) and keep the result in withoutLast. The helper is written after rob, and it solves House Robber for the houses from start to end.
    4. Leave out the first house. Call robRange(nums, 1, n - 1) and keep it in withoutFirst.
    5. Return the larger of the two with Math.max.
    6. Write robRange(nums, start, end), returning the best total for that range of houses, treated as a street.
    7. Start prev at 0. It is the best total up to two houses before the current one. Before the first house of the range nothing has been robbed.
    8. Start curr at 0. It is the best total up to the house just before the current one.
    9. Loop with i from start to end, both included, so the condition is i <= end.
    10. Compute best, the larger of curr (skip house i) and prev + nums[i] (rob it).
    11. Slide the totals along: set prev to curr first, then curr to best. The order matters, because changing curr first would lose the value prev needs.
    12. Return curr, the best total for the whole range.

    The solution in Java

    class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int withoutLast = robRange(nums, 0, n - 2);
        int withoutFirst = robRange(nums, 1, n - 1);
        return Math.max(withoutLast, withoutFirst);
    }

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

    Details worth a closer look:

    • Inclusive bounds. robRange treats end as part of the range, hence i <= end. The calls pass n - 2 and n - 1, the last index of each street.
    • No array copy. The helper reads the same array through its bounds, so the two cases cost no extra memory.
    • An empty range is safe. If start is greater than end, the loop doesn't run and the helper returns 0. With the early return for n == 1, that never happens here: two houses give ranges of one house each.
    • Methods call each other by name. rob calls robRange directly, and it doesn't matter that robRange is written below it. The helper has no public modifier, so it is package-private, which is fine inside one class.

    The two totals on [1, 2, 3, 1] are real results of the helper: robRange(nums, 0, 2) gives 4 (houses 0 and 2) and robRange(nums, 1, 3) gives 3 (house 1 and house 3, or house 2 alone). On [400, 0, 0, 400, 0, 0, 400] both cases give 800, while the whole array treated as a street, robRange(nums, 0, 6), gives 1200. The 400 gap is the cost of the circle.

    Complexity

    Time: O(n). Each of the two calls to robRange loops over at most n - 1 houses with a constant amount of work per house.

    Space: O(1). The code uses a few integer variables and no table.

    Edge cases and common mistakes

    • One house. [5] returns 5. Without the n == 1 check, robRange(nums, 0, -1) would return 0 and the other range would start past the end, so the answer would be 0 instead of 5.
    • Two houses. [3, 7] returns 7: they are neighbours, so you pick the richer one. The two ranges are the single houses 0 and 1.
    • Treating the circle as a street. Solving the plain problem on the whole array gives 1200 for the third example, which breaks the rule about the first and last house.
    • Zeros. [0, 0] gives 0. Money is never negative, so doing nothing is always an option and the totals never drop below 0.
    • Off-by-one in the ranges. Using n - 1 as the end of the first range puts the last house back in. Using 0 as the start of the second puts the first house back in.

    Testing

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