Start learning free

LESSON 449 OF 540 · DYNAMIC PROGRAMMING

House Robber II in Scala: 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

    SCALA · DYNAMIC PROGRAMMING

    House Robber Ii in Scala, explained

    Problem overview

    rob receives an Array[Int], nums, where nums(i) is the money in house i, and returns the most money you can take without robbing two neighbouring houses. The houses stand in a circle, so the last house is also next to house 0, and those two can't both be robbed.

    For [2, 3, 2] the answer is 3: houses 0 and 2 hold 2 each but are neighbours in the circle, so the best plan is house 1 alone. For [1, 2, 3, 1] the answer is 4, from houses 0 and 2. For [400, 0, 0, 400, 0, 0, 400] the answer is 800. Houses 0, 3 and 6 would give 1200 on a street with two ends, and the same array run as a plain street does give 1200, but in the circle houses 6 and 0 touch, so only two of the three can be taken.

    Approach: turn the circle into two streets

    On a street with two ends, the problem is the classic House Robber. Walking from left to right, the best total up to house i is either the best total up to house i - 1 (skip house i) or the best total up to house i - 2 plus nums(i) (rob house i, which forces house i - 1 to be skipped). Only the last two totals are needed, so two variables are enough.

    The circle adds one rule: the first and the last house can't both be robbed. So every valid plan leaves out the first house, the last house, or both. That gives two cases, and each one is an ordinary 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.

    A plan that leaves out both ends fits both streets, which does no harm: the answer is the larger of the two results. Each street takes one pass, so the total is O(n).

    Step by step

    1. Store the length in val n = nums.length.
    2. Handle one house. If n == 1, return nums(0). A single house has no neighbour, and each of the two streets below would be empty.
    3. Leave out the last house. val withoutLast = robRange(nums, 0, n - 2), assuming the helper exists for now.
    4. Leave out the first house. val withoutFirst = robRange(nums, 1, n - 1).
    5. Return the larger with math.max(withoutLast, withoutFirst) as the last expression.
    6. Write the helper's header. robRange takes nums, start and end and returns an Int: the best total for houses start to end on a street with two ends.
    7. var prev = 0: the best total up to two houses before the current one.
    8. var curr = 0: the best total up to the house just before the current one. Before the first house of the range nothing has been robbed, so both start at 0.
    9. Loop with i <- start to end. The range to includes end.
    10. Compute the best total up to house i: val best = math.max(curr, prev + nums(i)).
    11. Shift the totals. Set prev = curr first, then curr = best. The order matters: changing curr first would overwrite the value prev needs.
    12. Return curr after the loop, as the last expression.

    The solution in Scala

    class Solution {

    def rob(nums: Array[Int]): Int = {
        val n = nums.length
        if (n == 1) {
            return nums(0)
        }
        val withoutLast = robRange(nums, 0, n - 2)
        val withoutFirst = robRange(nums, 1, n - 1)
        math.max(withoutLast, withoutFirst)
    }

    def robRange(nums: Array[Int], start: Int, end: Int): Int = {
        var prev = 0
        var curr = 0
        for (i <- start to end) {
            val best = math.max(curr, prev + nums(i))
            prev = curr
            curr = best
        }
        curr
    }
}

    Here is robRange on the houses 0 to 1 of [2, 3, 2] (the case without the last house), as the loop runs:

    i=0 prev=0 curr=0 best=2
i=1 prev=0 curr=2 best=3

    The result is 3. And on houses 0 to 2 of [1, 2, 3, 1]:

    i=0 prev=0 curr=0 best=1
i=1 prev=0 curr=1 best=2
i=2 prev=1 curr=2 best=4

    That gives 4, which is the answer for that array.

    Scala details worth knowing:

    • The last expression is the result. math.max(withoutLast, withoutFirst) and curr have no return in front of them. The early return nums(0) inside the if leaves the method sooner, which is the one place the code needs it.
    • to versus until. start to end includes end, while start until end stops before it. When end is smaller than start, the range is empty and the loop doesn't run: robRange(Array(5, 6), 1, 0) returns 0.
    • val and var. prev and curr are var because they change on every round. best is a val, created fresh inside each round of the loop.
    • Ints are enough. With at most 100 houses of at most 1000 each, the total can't pass 100,000, far below the 32-bit limit.
    • Method order. rob can call robRange although it is defined below it. Methods of a class see each other in any order.

    Complexity

    Time: O(n). robRange runs once for n - 1 houses and once more for n - 1 houses, each with constant work per house, so each house is visited at most twice.

    Space: O(1). Only n, the two results and the two running totals are stored.

    Edge cases and common mistakes

    • A single house. [5] gives 5. Without the n == 1 check, the two streets would be empty and the answer would be 0.
    • Two houses. They are neighbours, so only one can be robbed: [1, 2] gives 2. Each street has one house (houses 0 to 0 and 1 to 1), and the larger one wins.
    • All zeros. [0, 0] gives 0. Nothing special is needed; 0 is the right starting total.
    • Solving it as a street. Running the street version on the whole array gives 1200 for [400, 0, 0, 400, 0, 0, 400], which robs two neighbouring houses of the circle. The correct answer is 800.
    • Dropping both ends. Skipping house 0 and the last house in one run can miss the best plan. In [1, 2, 3] the best is house 2 alone for 3, and a run over house 1 only would give 2.
    • Updating in the wrong order. Writing curr = best before prev = curr makes prev equal best too, and the totals stop being two houses apart.
    • Off-by-one on the ranges. The two ranges are 0 to n - 2 and 1 to n - 1, both inclusive. Using until with these values would drop a house.

    Testing

    Results from running the solution:

    numsWithout the last houseWithout the first houserob
    [2, 3, 2]333
    [1, 2, 3, 1]434
    [400, 0, 0, 400, 0, 0, 400]800800800
    [5]not usednot used5
    [1, 2]122
    [1, 2, 3]233
    [1000, 1, 1, 1000]100110011001
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free