Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Examples:
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3Solution in Python
Python
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
# Helper function to calculate the maximum money that can be robbed
# from a linear arrangement of houses
def rob_linear(houses: List[int]) -> int:
prev1, prev2 = 0, 0
for money in houses:
# Calculate the maximum money that can be robbed up to the current house
current = max(prev1, prev2 + money)
# Update prev2 and prev1 for the next iteration
prev2 = prev1
prev1 = current
return prev1
# If there is only one house, return the amount in that house
if len(nums) == 1:
return nums[0]
# Since the houses are in a circle, we can't rob both the first and last houses.
# Thus, we consider two cases:
# 1. Rob from the first house to the second-last house
# 2. Rob from the second house to the last house
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))Explanation:
- Linear Robbery Function:
rob_linear(houses: List[int]) -> int: This helper function is designed to handle the robbery problem for a linear arrangement of houses.- We use two variables,
prev1andprev2, to keep track of the maximum money that can be robbed up to the current house, and up to the previous house, respectively. - For each house, we calculate the maximum money we can rob by either skipping this house or robbing it and adding its value to the maximum money robbed two houses before.
- We return
prev1as the maximum amount of money that can be robbed from this linear arrangement of houses.
- Circular Robbery Problem:
- Since the houses are arranged in a circle, you cannot rob both the first and the last house because they are adjacent.
- We break down the problem into two linear scenarios:
- Rob from the first house to the second-last house (
nums[:-1]). - Rob from the second house to the last house (
nums[1:]).
- Rob from the first house to the second-last house (
- The final answer will be the maximum of these two scenarios.
- Edge Case:
- If there’s only one house, return the value of that house immediately as there’s no other option.
This approach ensures that you can maximize the amount of money robbed without alerting the police, even with the circular arrangement of houses.
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
// Helper function to calculate the maximum money that can be robbed
// from a linear arrangement of houses
const robLinear = (houses) => {
let prev1 = 0, prev2 = 0;
for (let money of houses) {
// Calculate the maximum money that can be robbed up to the current house
let current = Math.max(prev1, prev2 + money);
// Update prev2 and prev1 for the next iteration
prev2 = prev1;
prev1 = current;
}
return prev1;
};
// If there is only one house, return the amount in that house
if (nums.length === 1) {
return nums[0];
}
// Since the houses are in a circle, we can't rob both the first and last houses.
// Thus, we consider two cases:
// 1. Rob from the first house to the second-last house
// 2. Rob from the second house to the last house
return Math.max(robLinear(nums.slice(0, nums.length - 1)), robLinear(nums.slice(1)));
};Solution in Java
Java
import java.util.Arrays;
class Solution {
// Helper function to calculate the maximum money that can be robbed
// from a linear arrangement of houses
private int robLinear(int[] houses) {
int prev1 = 0, prev2 = 0;
for (int money : houses) {
// Calculate the maximum money that can be robbed up to the current house
int current = Math.max(prev1, prev2 + money);
// Update prev2 and prev1 for the next iteration
prev2 = prev1;
prev1 = current;
}
return prev1;
}
public int rob(int[] nums) {
// If there is only one house, return the amount in that house
if (nums.length == 1) {
return nums[0];
}
// Since the houses are in a circle, we can't rob both the first and last houses.
// Thus, we consider two cases:
// 1. Rob from the first house to the second-last house
// 2. Rob from the second house to the last house
return Math.max(
robLinear(Arrays.copyOfRange(nums, 0, nums.length - 1)),
robLinear(Arrays.copyOfRange(nums, 1, nums.length))
);
}
}Solution in C#
C#
public class Solution {
// Helper function to calculate the maximum money that can be robbed
// from a linear arrangement of houses
private int RobLinear(int[] houses) {
int prev1 = 0, prev2 = 0;
foreach (int money in houses) {
// Calculate the maximum money that can be robbed up to the current house
int current = Math.Max(prev1, prev2 + money);
// Update prev2 and prev1 for the next iteration
prev2 = prev1;
prev1 = current;
}
return prev1;
}
public int Rob(int[] nums) {
// If there is only one house, return the amount in that house
if (nums.Length == 1) {
return nums[0];
}
// Since the houses are in a circle, we can't rob both the first and last houses.
// Thus, we consider two cases:
// 1. Rob from the first house to the second-last house
// 2. Rob from the second house to the last house
return Math.Max(
RobLinear(nums[0..^1]), // nums[0..^1] is equivalent to nums.slice(0, nums.Length - 1)
RobLinear(nums[1..]) // nums[1..] is equivalent to nums.slice(1, nums.Length)
);
}
}