Start learning free

LESSON 449 OF 540 · DYNAMIC PROGRAMMING

House Robber II in Go: 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 <= len(nums) <= 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

Guided

Ctrl + Enter to check

GO · DYNAMIC PROGRAMMING

House Robber Ii in Go, explained

Problem overview

The function rob receives a slice nums where nums[i] is the money in house i. The houses stand in a circle, so the last house is the neighbour of house 0. Robbing two neighbouring houses on the same night alerts the police. The function returns the largest total that can be robbed without robbing two neighbours.

In the first example, nums = [2, 3, 2]. Houses 0 and 2 both hold 2, but they are neighbours in the circle, so they can't both be robbed. The best plan is house 1 alone, for 3. In the second example, nums = [1, 2, 3, 1]: houses 0 and 2 give 1 + 3 = 4. In the third, nums = [400, 0, 0, 400, 0, 0, 400], the houses 0, 3 and 6 would give 1200 on a street with two ends, but in the circle house 6 touches house 0, so the answer is 800.

Approach: break the circle in two places

Without the circle, this is the classic House Robber problem: for each house, 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. The circle adds a single rule: the first and the last house can't both be robbed.

That rule gives a neat split. Every valid plan leaves out the first house or the last house (or both). So there are two cases, and each one is a street with two ends:

Leave out the last house: solve the street of houses 0 to n - 2.
Leave out the first house: solve the street of houses 1 to n - 1.

The answer is the larger of the two results. A plan that robs neither end appears in both cases, which is harmless: only the best total matters. Each case is solved in one pass with two running totals, so the whole solution takes O(n) time and O(1) extra space, as the statement asks. The helper robRange solves the linear problem on part of the slice.

A single house is a special case. It has no neighbour, so you rob it. Both ranges above would be empty for n == 1, and the answer would be 0 instead of the house's money.

Step by step

Store the number of houses in n := len(nums).
Handle one house. If n == 1, return nums[0].
Leave out the last house. withoutLast := robRange(nums, 0, n-2) solves the street from house 0 to house n - 2. Writing the helper afterwards keeps rob short.
Leave out the first house. withoutFirst := robRange(nums, 1, n-1) breaks the circle at the other end.
Return the larger result with max(withoutLast, withoutFirst).
Declare the helper. robRange takes nums []int, start int and end int, and returns an int: the most money from houses start to end, robbed as a street with two ends.
Create prev := 0: the best total from the houses of the range up to two houses before the current one.
Create curr := 0: the best total up to the house just before the current one. Both start at 0 because nothing has been robbed before the range.
Visit the houses with for i := start; i <= end; i++. The condition is <=, because house end belongs to the range.
Compute the best total up to house i: best := max(curr, prev+nums[i]). Either skip house i and keep curr, or rob it, which means house i - 1 stays untouched, so its money joins prev.
Shift the totals by one house: prev = curr, then curr = best. The order matters, because changing curr first would overwrite the value prev needs.
Return curr after the loop. It is the best total for the whole range.

The solution in Go

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    withoutLast := robRange(nums, 0, n-2)
    withoutFirst := robRange(nums, 1, n-1)
    return max(withoutLast, withoutFirst)
}

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

The Go details worth knowing:

Built-in max. Since Go 1.21, max and min are built-in functions that accept two or more values of the same ordered type. Older versions of Go need a hand-written helper, so the built-in is a feature of current Go.
Slices are not copied. robRange receives nums as a slice, which shares the same elements as the caller's slice. The helper reads from the original numbers and uses the indexes start and end to pick its part, so no sub-slices are created.
:= inside the loop. best is declared with := in each round, and it exists only inside that round's block. The two running totals are declared outside the loop so that they survive from one round to the next.
Unused variables are errors. Every variable you declare must be used. All four variables here (prev, curr, best, n) are read, so the code compiles.
Integer range. int is 64 bits, so sums of up to 100 houses with at most 1000 each never overflow.

Complexity

Time: O(n). robRange makes one pass over at most n - 1 houses with constant work per house, and rob calls it twice. Together the two calls visit each house at most twice.

Space: O(1). The function keeps a few integers and builds no table.

Edge cases and common mistakes

One house. [5] returns 5. Without the n == 1 check, both ranges are empty and the function would return 0.
Two houses. [1, 2] returns 2: they are neighbours, so only one can be robbed, and the better one wins. robRange(nums, 0, 0) and robRange(nums, 1, 1) give 1 and 2.
The circle matters. For [3, 1, 1, 3] the function returns 4. On a street with two ends the answer would be 6, from the two end houses, which are neighbours in the circle.
Money at the end. For [1, 3, 1, 3, 100] the answer is 103: the last house, plus house 1. The case that leaves out the first house finds it.
All zeros. [0, 0] returns 0.
Using < in the loop. The house end would be skipped, and the answer would be too small.
Updating the totals in the wrong order. Setting curr before prev makes both equal to the new total, and the "two houses back" value is lost.
Solving the straight street once. Running the linear solution on the whole slice ignores the link between the last house and the first.

Testing

nums = [2, 3, 2] gives 3.
nums = [1, 2, 3, 1] gives 4.
nums = [400, 0, 0, 400, 0, 0, 400] gives 800.
nums = [5] gives 5.
nums = [1, 2] gives 2.
nums = [3, 1, 1, 3] gives 4.
nums = [1, 3, 1, 3, 100] gives 103.
nums = [200, 3, 140, 20, 10] gives 340.

Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free