House Robber II
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
The houses are in a circle: the first and last are neighbours. Maximise the total without robbing two adjacent houses.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which two houses can never both be taken?
- Hint 2Split into two linear problems.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The same street, but it bends into a circle so house 1 touches the last house. Make two plans: Plan A pretends the last house does not exist (you may rob house 1), plan B pretends house 1 does not exist (you may rob the last). Each plan is the ordinary straight-street problem. The answer is the better plan.
- The obvious way
Try all subsets with the circular rule: O(2^n).
- The key insight
If there is one house, return it. Otherwise answer = max(rob_line(houses without the last), rob_line(houses without the first)), where rob_line is the straight-street solution.
- The algorithm
- One house: return its money.
- Line A: all houses except the last.
- Line B: all houses except the first.
- Answer = max of the two lines' best.
Watch it run
Examplenums = [2, 3, 2]
Line A ignores the last house: houses [2, 3]. Best is 3.
A = 3
Where people slip
- A single house must be handled separately, otherwise both lines are empty and return 0.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def rob(nums):
def rob_line(houses): # the ordinary straight street
best_two_back, best_one_back = 0, 0
for money in houses:
best_two_back, best_one_back = best_one_back, max(best_one_back, best_two_back + money)
return best_one_back
if len(nums) == 1:
return nums[0]
return max(rob_line(nums[:-1]), rob_line(nums[1:])) # without the last, or without the firstNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.