House robber
Goldman Sachs
Google
InfosysThe problem
A robber is targeting to rob houses from a street. Each house has security measures that alert the police when two adjacent houses are robbed. The houses are arranged in a circular manner, thus the first and last houses are adjacent to each other.
Given an integer array money, where money[i] represents the amount of money that can be looted from the (i+1)th house. Return the maximum amount of money that the robber can loot without alerting the police.
Input: money = [2, 1, 4, 9] Output: 10 Explanation: [2, 1, 4, 9] The underlined houses would give the maximum loot. Note that we cannot loot the 1st and 4th houses together.
Input: money = [1, 5, 2, 1, 6] Output: 11 Explanation: [1, 5, 2, 1, 6] The underlined houses would give the maximum loot.
Input: money = [9, 4, 1, 8]
- 1 <= money.length <= 105
- 0 <= money[i] <= 1000
cpp
class Solution {
public:
int houseRobber(vector<int>& money) {
}
};java
class Solution {
public int houseRobber(int[] money) {
}
}python
class Solution:
def houseRobber(self, money):javascript
class Solution {
houseRobber(money) {
}
}csharp
class Solution{
public int HouseRobber(List<int> money) {
}
}go
func houseRobber(money []int) int {
}Stuck? Show a way to structure it+
- 01Observe that a valid solution cannot rob both the first and last houses.
- 02Solve linear house robber once excluding the last house and once excluding the first.
- 03Return the larger result, handling the single-house case separately.
- 04Use the linear recurrence with two rolling states in each case.
Reference answer
Then expect these follow-ups
How would you return which houses were robbed?
Tests: reconstruction
Why do the two linear cases cover every valid circular solution?
Tests: case proof
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question