Problem overview
rob receives a vector nums, where nums[i] is the money in house i, and returns the most money you can take without robbing two neighbouring houses. This is House Robber with one change: the houses stand in a circle, so the last house is a neighbour of the first.
For [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each, but they are neighbours in the circle, so the best plan is house 1 alone. For [1, 2, 3, 1] it is 4, from houses 0 and 2. For [400, 0, 0, 400, 0, 0, 400] it is 800: on a street with two ends, houses 0, 3 and 6 would give 1200, but houses 6 and 0 are neighbours here, so only two of the three can be used.
Approach: break the circle into two streets
On a straight street, the classic solution keeps two running totals. Going house by house, the best total up to house i is the larger of "skip this house" (the previous best) and "rob this house" (its money plus the best from two houses back).
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 street problems:
- houses
0ton - 2(the last house left out), and - houses
1ton - 1(the first house left out).
Neither range contains both ends, so neither has a problem with the circle, and each one is the straight-street problem. The answer is the larger of the two results. A plan that robs neither end appears in both, which does no harm: only the best total counts.
One house is a special case, because the two ranges would be empty or invalid. With a single house, you rob it.
Step by step
- Store
nums.len()inn. It is ausize, the type Rust uses for indexes, son - 2andn - 1below are indexes too. - Return
nums[0]whenn == 1. A single house has no neighbour. The two ranges below each leave one house out, which would leave nothing. - Leave out the last house.
Self::rob_range(&nums, 0, n - 2)solves the street of houses 0 ton - 2. Assume the helper exists for now; writing it afterwards keepsrobshort. - Leave out the first house with
Self::rob_range(&nums, 1, n - 1). - Return the larger result with
without_last.max(without_first), with no semicolon. - Write
rob_rangewith a slice&[i32]and the first and last index of the street. It returns the best total for the houses fromstarttoend. - Create
prevaslet mut, set to 0: the best total up to two houses before the current one. - Create
currthe same way: the best total up to the house just before the current one. Both start at 0 because nothing has been robbed before the first house of the range. - Loop
ioverstart..=end. The..=includesend;..would stop one house early. - Compute
bestascurr.max(prev + nums[i]): skip housei, or rob it and add its money to the total from two houses back. - Move both totals one house to the right:
prev = curr;first, thencurr = best;. In the other order,prevwould receive the new value instead of the old one. - Return
currafter the loop.
The solution in Rust
impl Solution {
fn rob(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 {
return nums[0];
}
let without_last = Self::rob_range(&nums, 0, n - 2);
let without_first = Self::rob_range(&nums, 1, n - 1);
without_last.max(without_first)
}
fn rob_range(nums: &[i32], start: usize, end: usize) -> i32 {
let mut prev = 0;
let mut curr = 0;
for i in start..=end {
let best = curr.max(prev + nums[i]);
prev = curr;
curr = best;
}
curr
}
}
For [1, 2, 3, 1], the helper runs twice. The values of prev and curr after each house are:
houses 0..=2: i=0 prev=0 curr=1; i=1 prev=1 curr=2; i=2 prev=2 curr=4
houses 1..=3: i=1 prev=0 curr=2; i=2 prev=2 curr=3; i=3 prev=3 curr=3
The first street gives 4, the second 3, and rob returns 4.
Rust details worth a closer look:
- Slices.
rob_rangetakes&[i32], a borrowed view of a run of numbers.&nums, a reference to aVec<i32>, coerces to it, androbcan lend the vector twice because the helper only reads it. - Type inference.
prevandcurrstart as the literal 0. Rust infersi32fromprev + nums[i]and from the return type. maxis a method.curr.max(prev + nums[i])andwithout_last.max(without_first)return the larger of two integers.usizesubtraction.n - 2is only safe becausen == 1returned earlier, and the lesson's constraint saysnis at least 1. Ausizecan't go below zero: in a debug build1usize - 2panics, and in an optimized build it wraps to a huge number.- Last expressions.
without_last.max(without_first)andcurrhave no semicolon, so they are what the functions return.
Complexity
Time: O(n). Each call of rob_range visits at most n - 1 houses, and there are two calls.
Space: O(1). Only prev, curr and best are kept, instead of a whole table.
Edge cases and common mistakes
- One house.
[5]returns 5 through the early return. Without it,n - 2would be ausizeunderflow. - Two houses. They are neighbours, so you take the larger one: the ranges are
0..=0and1..=1.[5, 9]gives 9. - Treating the circle as a line. On
[400, 0, 0, 400, 0, 0, 400], a street solution gives 1200, but the circle allows 800. - Only checking one range. For
[1, 3, 1, 3, 100]the street without the last house gives 6 and the street without the first gives 103. For the mirrored[100, 3, 1, 3, 1]the results swap. Both ranges are needed, because the best plan may leave out either end. - Zeros. Houses with no money are fine:
[0, 0]gives 0. - Swapping the updates. Setting
curr = bestbeforeprev = currloses the oldcurr. - Stopping a house early. Writing
start..endinstead ofstart..=endskips the last house of each range.
Testing
[2, 3, 2]gives 3.[1, 2, 3, 1]gives 4.[400, 0, 0, 400, 0, 0, 400]gives 800.[5]gives 5.[5, 9]gives 9.[0, 0]gives 0.[1, 2, 3]gives 3.[200, 3, 140, 20, 10]gives 340.
