Problem overview
rob receives an array nums, where nums[i] is the money in house i, and returns the most money that can be robbed without taking from two neighbouring houses. The houses stand in a circle, so the last house is a neighbour of house 0.
For [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each, but they are neighbours in the circle, so only one of them can be taken, and house 1 alone (3) beats either of them. For [1, 2, 3, 1] the answer is 4: houses 0 and 2, giving 1 + 3.
Approach: break the circle into two streets
On a street with two ends, the classic solution keeps two running totals as it walks along. At each house, the best total is either the previous best (skip this house) or the best from two houses back plus this house's money (rob it).
The circle adds one rule: the first and last houses can't both be robbed. So every valid plan leaves out the first house, or the last one, or both. That gives two plain streets to solve: houses 0 to n - 2 (last house left out) and houses 1 to n - 1 (first house left out). The answer is the larger of the two results. A plan that robs neither end appears in both, which does no harm, as only the best total matters.
The need for this split shows on [2, 3, 2]: running the street solution over the whole array gives 4, which robs both ends and is not allowed in the circle. The two shorter streets, [2, 3] and [3, 2], both give 3.
Step by step
- Count the houses. Store
nums.countinn. - One house. If
n == 1, returnnums[0]. A single house has no neighbour, and both ranges below would be empty. - Leave out the last house.
withoutLastisrobRange(nums, 0, n - 2). The helper solves the street problem for housesstarttoend. - Leave out the first house.
withoutFirstisrobRange(nums, 1, n - 1). - Take the larger with
max. - The helper's signature.
robRange(_ nums: [Int], _ start: Int, _ end: Int) -> Int, with_before each name so the calls pass the values without labels. prev. A variable starting at 0: the best total up to two houses before the current one.curr. A variable starting at 0: the best total up to the house just before the current one.- Loop
iover the closed rangestart...end. - Decide house
i.bestis the larger ofcurr(skip it) andprev + nums[i](rob it). - Shift the totals. Set
prevtocurrfirst, thencurrtobest. The other order would overwrite the valueprevneeds. - Return
curr, the best total for the whole range.
The solution in Swift
class Solution {
func rob(_ nums: [Int]) -> Int {
let n = nums.count
if n == 1 {
return nums[0]
}
let withoutLast = robRange(nums, 0, n - 2)
let withoutFirst = robRange(nums, 1, n - 1)
return max(withoutLast, withoutFirst)
}
func robRange(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
var prev = 0
var curr = 0
for i in start...end {
let best = max(curr, prev + nums[i])
prev = curr
curr = best
}
return curr
}
}
The Swift details worth a closer look:
- Closed ranges must not run backwards.
start...endincludesend, and Swift crashes at run time whenendis smaller thanstart. With one house,robRange(nums, 0, -1)would build such a range, which is whyrobreturns early whenn == 1. From two houses on, both calls havestart <= end. varandlet.prevandcurrchange in the loop, so they arevar.bestis computed once per round, so it islet.- The global
max.max(a, b)is a free function in Swift's standard library, not a method on a number. - Unlabelled parameters. Because of the
_,robRange(nums, 0, n - 2)needs nostart:orend:labels. Without it, the call would not compile. - Arrays are passed without copying.
numsis a value type, but the helper only reads it, so no copy of the elements is made.
Complexity
Time: O(n). The two calls to robRange each walk at most n - 1 houses with constant work per house.
Space: O(1). The code keeps a few integers and builds no table.
Edge cases and common mistakes
- One house.
[5]returns 5. Without the early return, the helper would get an empty range that Swift can't build. - Two houses.
[2, 3]returns 3. The two ranges are each a single house, so the answer is the larger of the two, as the circle requires: they are neighbours. - Treating the circle as a street. For
[400, 0, 0, 400, 0, 0, 400]the street answer is 1200, which robs both ends. The circle answer is 800. - Zeros.
[0, 0]returns 0. The money is never negative, so doing nothing is always an option. - Updating in the wrong order. Assigning
curr = bestbeforeprev = currmakes both totals equal and breaks the next round. - Using
n - 1as the first call's end. That includes the last house, and the first call would then be able to rob both ends.
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, 3]and[3, 2]both give 3.[1, 1, 1]gives 1: any two of the three houses are neighbours in the circle.[5, 1, 1, 5]gives 6: the two 5s are neighbours in the circle, so one 5 and one 1.
