Start learning free

LESSON 449 OF 540 · DYNAMIC PROGRAMMING

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

    KOTLIN · DYNAMIC PROGRAMMING

    House Robber Ii in Kotlin, explained

    Problem overview

    The houses stand in a circle. Each holds some money, given in the array nums, and two neighboring houses can't both be robbed. Because the street is a circle, house 0 and the last house are neighbors. rob(nums) returns the most money you can take.

    For nums = [2, 3, 2] the answer is 3: the two houses with 2 are neighbors in the circle, so you rob the middle one. 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. On a street with two ends the three houses worth 400 would give 1200, but in a circle the first and last are neighbors, so only two of them can be taken.

    Approach

    On a street with two ends, the problem has a standard running-totals solution: for each house, the best total is either the best total without it, or its money plus the best total two houses back. The circle adds one rule: the first and last house can't both be robbed.

    That rule gives a neat split. Any valid plan leaves out the first house or the last house (or both). So:

    • Plans that leave out the last house are plans on houses 0 to n - 2, a plain street.
    • Plans that leave out the first house are plans on houses 1 to n - 1, also a plain street.

    Solve both streets, and take the larger result. A plan that robs neither end appears in both, which does no harm, since we only want the best total. The circle has become two ordinary problems, each solved in one pass.

    Step by step

    The circle, rob

    1. Count the houses. Store nums.size in val n.
    2. One house. If n == 1, return nums[0]. A lone house has no neighbor, so you take it. This case must come first: both ranges below would leave that house out and be empty.
    3. Without the last house. val withoutLast = robRange(nums, 0, n - 2).
    4. Without the first house. val withoutFirst = robRange(nums, 1, n - 1).
    5. Take the better one with maxOf(withoutLast, withoutFirst).

    The street, robRange

    1. Two totals. var prev = 0 is the best total up to two houses before the current one, and var curr = 0 the best total up to the house just before it. Both start at 0, since nothing has been robbed before the first house of the range.
    2. Loop with i over start..end. This range includes both ends, so house end is visited.
    3. Decide house i. val best = maxOf(curr, prev + nums[i]): either skip house i and keep curr, or rob it, which requires leaving house i - 1 alone, so its money goes on top of prev.
    4. Shift. Set prev = curr first, then curr = best. Doing it the other way round would overwrite the value that prev needs.
    5. After the loop, curr is the best total for the whole range. Return it.

    The solution in Kotlin

    class Solution {

    fun rob(nums: IntArray): Int {
        val n = nums.size
        if (n == 1) {
            return nums[0]
        }
        val withoutLast = robRange(nums, 0, n - 2)
        val withoutFirst = robRange(nums, 1, n - 1)
        return maxOf(withoutLast, withoutFirst)
    }

    fun robRange(nums: IntArray, start: Int, end: Int): Int {
        var prev = 0
        var curr = 0
        for (i in start..end) {
            val best = maxOf(curr, prev + nums[i])
            prev = curr
            curr = best
        }
        return curr
    }
}

    Kotlin details worth knowing

    • start..end is inclusive. Both ends are visited. When end is smaller than start, the range is empty and the loop body never runs: robRange(intArrayOf(7, 9), 1, 0) returns 0.
    • maxOf. maxOf(a, b) is a standard-library function for two values. There is no need for an if or an import.
    • val inside the loop. best is a new val in every round, because it never changes after it is set. The two running totals are var, because they change each round.
    • Arrays are passed by reference. robRange receives the same IntArray and only reads from it. Nothing is copied, even though the helper looks at "a part" of the array: the two integers start and end say which part.
    • Both methods are members of the class. rob calls robRange by its plain name, and the order of the two functions in the class doesn't matter in Kotlin.

    Complexity

    • Time: O(n). Each of the two calls to robRange loops over at most n - 1 houses with constant work per house, so the total is about 2n steps.
    • Space: O(1). Only a few Int variables, no table: the two running totals replace an array of best totals.

    Edge cases and common mistakes

    • One house. [5] gives 5. Without the n == 1 check the range 0..-1 would be empty and the answer would wrongly be 0.
    • Two houses. [1, 2] gives 2: the houses are neighbors, so you take the richer one. The two ranges are each a single house, worth 1 and 2.
    • Solving it as a plain street. The answer for [400, 0, 0, 400, 0, 0, 400] on a street is 1200, but the circle's answer is 800. Ignoring the link between the ends gives the wrong number whenever both ends are used.
    • Including the wrong ends. The two ranges are 0..n - 2 and 1..n - 1. Using 0..n - 1 for one of them brings back the street answer.
    • Overwriting prev too early. Setting curr = best before prev = curr loses the old curr.
    • All zeros. The answer is 0, not negative: the totals start at 0 and the values are never negative.

    Testing

    These results come from running the solution above, with the two ranges' results shown to see which one wins:

    numsWithout lastWithout firstrob
    [2, 3, 2]333
    [1, 2, 3, 1]434
    [400, 0, 0, 400, 0, 0, 400]800800800
    [1, 2]122
    [2, 1, 1, 2]333
    [5]not usednot used5
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free