Start learning free

LESSON 445 OF 536 · DYNAMIC PROGRAMMING

House Robber II in JavaScript: Circular Street in O(n)

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

    JAVASCRIPT · DYNAMIC PROGRAMMING

    House Robber Ii in JavaScript, explained

    Problem overview

    rob(nums) receives an array where nums[i] is the money in house i. The houses stand in a circle, so the last house is a neighbor of house 0. Robbing two neighboring houses on the same night alerts the police. The function returns the most money that can be robbed without that. This is House Robber with one change: the first and the last house can't both be robbed.

    For nums = [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each, but they are neighbors in the circle, so the best plan robs house 1 only. For nums = [1, 2, 3, 1] the answer is 4: houses 0 and 2 give 1 + 3. For [400, 0, 0, 400, 0, 0, 400] a straight street would allow 1200 from houses 0, 3 and 6, but in the circle houses 6 and 0 touch, so the answer is 800.

    Approach: break the circle into two streets

    On a street with two ends, the standard method keeps two running totals while it walks along: the best total for the houses up to the previous one, and up to the one before that. At each house the choice is to skip it (keep the previous total) or rob it (add its money to the total from two houses back, since the neighbor must stay untouched).

    The circle adds one rule: houses 0 and n - 1 are not both robbed. So every valid plan leaves out the first house or the last one (or both). That gives two straight-street problems:

    • houses 0 to n - 2, with the last house left out;
    • houses 1 to n - 1, with the first house left out.

    The best plan is in one of them, so the answer is the larger of the two results. A plan that robs neither end fits both, which does no harm: only the best total matters. A single house is a special case, because both ranges would be empty, and its answer is just its money.

    On [1, 2, 3, 1], leaving out the last house means the street [1, 2, 3], which gives 4. Leaving out the first means [2, 3, 1], which gives 3. The larger, 4, is the answer.

    Step by step

    1. Store the length in const n = nums.length.
    2. One house: if n === 1, return nums[0]. A single house has no neighbor, so it is robbed.
    3. Leave out the last house: withoutLast is this.robRange(nums, 0, n - 2). A method calls another method of the same object through this.
    4. Leave out the first house: withoutFirst is this.robRange(nums, 1, n - 1).
    5. Take the better one with Math.max(withoutLast, withoutFirst).
    6. Write the helper robRange(nums, start, end), the street version on part of the array.
    7. prev is a let variable starting at 0: the best total up to two houses before the current one.
    8. curr is a let variable starting at 0: the best total up to the house just before the current one.
    9. Loop with let i = start while i <= end. The condition is <= because house end belongs to the range.
    10. Compute the best total including house i as Math.max(curr, prev + nums[i]), stored in const best: skip it, or rob it and add to prev.
    11. Shift the totals: prev = curr first, then curr = best. In the other order, prev would get the new value.
    12. Return curr, the best total for the whole range.

    The solution in JavaScript

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

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

    Details worth knowing:

    • const and let. prev and curr change in the loop, so they need let. best is made again in each pass of the loop, so const works for it.
    • ===. n === 1 compares without converting types. For numbers it behaves like ==, but it is the habit worth keeping.
    • The range is inclusive. Both start and end are houses to visit. For n = 2, the calls are robRange(nums, 0, 0) and robRange(nums, 1, 1), one house each.
    • An empty range gives 0. The loop doesn't run, so curr is still 0. This case doesn't come up, because n === 1 returns first.

    Complexity

    Time: O(n). Each call of robRange visits at most n - 1 houses with constant work each, and rob makes two calls.

    Space: O(1). Only a few numbers are kept, with no table.

    Edge cases and common mistakes

    • One house. [5] gives 5. Without the special case, robRange(nums, 0, -1) and robRange(nums, 1, 0) would both return 0.
    • Two houses. [2, 7] gives 7: they are neighbors, so only the richer one is robbed.
    • All zeros. [0, 0] gives 0.
    • Using the plain street answer. For [400, 0, 0, 400, 0, 0, 400] a street-only solution returns 1200 instead of 800. Running it on the whole array gives exactly that.
    • < instead of <=. The last house of each range would be skipped.
    • Updating curr before prev. Then prev copies the new value, and the totals are wrong.

    Testing

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