Start learning free

LESSON 449 OF 540 · DYNAMIC PROGRAMMING

House Robber II in TypeScript: Circular Street in O(n) Time

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

    TYPESCRIPT · DYNAMIC PROGRAMMING

    House Robber Ii in TypeScript, explained

    Problem overview

    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 neighbor of the first. Robbing two neighboring houses on the same night alerts the police. The function returns the largest total you can rob without robbing two neighbors.

    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 is to rob house 1 alone. For [1, 2, 3, 1] the answer is 4: rob houses 0 and 2 for 1 + 3.

    The statement sets an O(n) time budget.

    Approach: break the circle in two places

    On a straight street with two ends, the problem is the classic House Robber. At each house you either skip it and keep the best total so far, or rob it and add its money to the best total from two houses back. That needs only two running numbers.

    The circle adds exactly one rule: the first and the last house can't both be robbed. So every valid plan leaves out the first house, or the last one, or both. That gives two straight streets:

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

    Each of them has two ends, so the straight-street method solves it. A plan that skips both end houses fits both streets, which does no harm because we only want the maximum. The answer is the larger of the two results.

    A lone house is a special case. It has no neighbor, so you rob it, but both streets above would be empty. That's why the solution handles n == 1 first.

    The straight-street method visits each house once, and we run it twice, so the total is O(n).

    Step by step

    1. Count the houses. Store nums.length in const n.
    2. One house. If n === 1, return nums[0].
    3. Leave out the last house. this.robRange(nums, 0, n - 2) gives withoutLast. We use the helper before writing it, which keeps rob short. Inside a class, one method calls another through this.
    4. Leave out the first house. this.robRange(nums, 1, n - 1) gives withoutFirst.
    5. Take the better one with Math.max.
    6. The helper. robRange(nums, start, end) returns the best total for houses start to end, treated as a street with two ends.
    7. Two running totals. prev and curr, both let and both starting at 0. At the start of each round, curr is the best total for the houses before house i, and prev the best for the houses before house i - 1.
    8. The loop. i runs from start up to and including end, so it uses <=.
    9. The choice. best = Math.max(curr, prev + nums[i]): skip house i and keep curr, or rob it and add its money to prev, leaving house i - 1 alone.
    10. Shift. Set prev = curr first, then curr = best. The reverse order would overwrite the value prev needs.
    11. Return curr after the loop.

    The solution in TypeScript

    class Solution {

    rob(nums: number[]): number {
        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: number[], start: number, end: number): number {
        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;
    }
}

    TypeScript details

    • let prev = 0; needs no annotation: TypeScript infers number from the initial value. const is used for values that never change, and let for the two totals that do.
    • number is a double, so there is no integer overflow. With at most 100 houses of at most 1000 each, totals stay far below the point where doubles lose integer precision.
    • === compares without type conversion and is the usual choice in TypeScript.
    • When the range is empty (end < start), the loop body never runs and robRange returns 0. For example robRange([5], 0, -1) returns 0.

    Tracing an example

    For nums = [1, 2, 3, 1], the first street is houses 0 to 2. Running the loop prints these values:

    inums[i]prevcurrbest
    01001
    12012
    23124

    So withoutLast is 4. The second street, houses 1 to 3, gives best values 2, 3 and 3, so withoutFirst is 3. The larger one, 4, is the answer.

    Complexity

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

    Space: O(1). Only a few variables are used, whatever the number of houses.

    Edge cases and common mistakes

    • A single house. [5] returns 5. Without the early return, both calls would get an empty range and the answer would be 0.
    • Two houses. They are neighbors in both directions, so you can rob only one. For [1, 2], the first street is just house 0 (1), the second is house 1 (2), and the result is 2.
    • Solving it as a plain street. For [400, 0, 0, 400, 0, 0, 400], a street with two ends gives 1200, but the circle only allows 800.
    • Using < instead of <= in the loop. The last house of the range would be skipped.
    • Updating the totals in the wrong order. Assign curr = best before prev = curr and both end up equal to best.
    • Zeros. Houses may hold 0. [0, 0, 0] returns 0, which is correct.

    Testing

    Running rob on a few arrays gives:

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