House Robber II
House Robber 2 – Medium Level Problem
You are given an array of integers nums, where nums[i] represents the amount of money in the (i)th house. The houses are arranged in a circle, meaning the first and last houses are neighbors.
You plan to rob some houses, but you cannot rob two adjacent houses because doing so will trigger the security system and alert the police.
Your task is to find the maximum amount of money you can rob without triggering the security system.
Example 1
Input: nums = [3,4,3]
Output: 4
Output: 4
Explanation:
- You can’t rob nums[0] + nums[2] = 6 because nums[0] and nums[2] are adjacent houses.
- Maximum you can rob is nums[1] = 4.
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Algorithm for Solving House Robber 2 Problem
1. Handle Edge Cases:
If there’s only one house, return its value. If there are two houses, return the maximum of the two.
2. Divide into Two Scenarios:
- Scenario 1: Consider houses from the first to the second-last.
- Scenario 2: Consider houses from the second to the last.
3. Use the House Robber Algorithm:
Apply the regular House Robber approach (linear) to calculate the maximum money for both scenarios.
4. Compare Results:
Take the maximum value between the two scenarios.
5. Return the Result:
The maximum value is the most money you can rob without alerting the police.
House Robber 2 Solution
There are mainly 4 approach to solve this problem-
- Recursion Method
- Dynamic Programming Top Down Method
- Dynamic Programming Bottom Up Method
- Dynamic Programming Space Optimized Method
1. Recursion Method
Solve the problem by splitting it into two cases—robbing houses excluding the first or excluding the last—then use recursion to find the maximum money in each case.
- Time complexity: O(2^n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int rob(vector& nums) {
if (nums.size() == 1) return nums[0];
return max(dfs(0, true, nums), dfs(1, false, nums));
}
private:
int dfs(int i, bool flag, vector& nums) {
if (i >= nums.size() || (flag && i == nums.size() - 1))
return 0;
return max(dfs(i + 1, flag, nums),
nums[i] + dfs(i + 2, flag || i == 0, nums));
}
};
Java
public class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(dfs(0, true, nums), dfs(1, false, nums));
}
private int dfs(int i, boolean flag, int[] nums) {
if (i >= nums.length || (flag && i == nums.length - 1))
return 0;
return Math.max(dfs(i + 1, flag, nums),
nums[i] + dfs(i + 2, flag || i == 0, nums));
}
}
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
def dfs(i, flag):
if i >= len(nums) or (flag and i == len(nums) - 1):
return 0
return max(dfs(i + 1, flag),
nums[i] + dfs(i + 2, flag or i == 0))
return max(dfs(0, True), dfs(1, False))JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
rob(nums) {
if (nums.length === 1) return nums[0];
const dfs = (i, flag) => {
if (i >= nums.length || (flag && i === nums.length - 1))
return 0;
return Math.max(dfs(i + 1, flag),
nums[i] + dfs(i + 2, flag || i === 0));
}
return Math.max(dfs(0, true), dfs(1, false));
}
}
2. Dynamic programming Top Down Method
Combine recursion with memorization to handle the circular arrangement of houses, storing intermediate results for both cases to avoid overlapping calculations.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
vector> memo;
public:
int rob(vector& nums) {
if (nums.size() == 1) return nums[0];
memo.resize(nums.size(), vector(2, -1));
return max(dfs(0, 1, nums), dfs(1, 0, nums));
}
private:
int dfs(int i, int flag, vector& nums) {
if (i >= nums.size() || (flag == 1 && i == nums.size() - 1))
return 0;
if (memo[i][flag] != -1)
return memo[i][flag];
memo[i][flag] = max(dfs(i + 1, flag, nums),
nums[i] + dfs(i + 2, flag | (i == 0 ? 1 : 0), nums));
return memo[i][flag];
}
};
Java
public class Solution {
private int[][] memo;
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
memo = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
memo[i][0] = -1;
memo[i][1] = -1;
}
return Math.max(dfs(0, 1, nums), dfs(1, 0, nums));
}
private int dfs(int i, int flag, int[] nums) {
if (i >= nums.length || (flag == 1 && i == nums.length - 1))
return 0;
if (memo[i][flag] != -1)
return memo[i][flag];
memo[i][flag] = Math.max(dfs(i + 1, flag, nums),
nums[i] + dfs(i + 2, flag | (i == 0 ? 1 : 0), nums));
return memo[i][flag];
}
}
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
memo = [[-1] * 2 for _ in range(len(nums))]
def dfs(i, flag):
if i >= len(nums) or (flag and i == len(nums) - 1):
return 0
if memo[i][flag] != -1:
return memo[i][flag]
memo[i][flag] = max(dfs(i + 1, flag),
nums[i] + dfs(i + 2, flag or (i == 0)))
return memo[i][flag]
return max(dfs(0, True), dfs(1, False))
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
rob(nums) {
if (nums.length === 1) return nums[0];
const n = nums.length;
const memo = Array.from({ length: n }, () => Array(2).fill(-1));
const dfs = (i, flag) => {
if (i >= n || (flag && (i === n - 1)))
return 0;
if (memo[i][flag] !== -1)
return memo[i][flag];
memo[i][flag] = Math.max(
dfs(i + 1, flag),
nums[i] + dfs(i + 2, flag | (i === 0))
);
return memo[i][flag];
}
return Math.max(dfs(0, 1), dfs(1, 0));
}
}
3. Dynamic Programming Bottom Up Method
Break the problem into two linear scenarios (excluding first or last house) and calculate maximum money iteratively by building from smaller sub problems.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int rob(std::vector& nums) {
if (nums.size() == 1) return nums[0];
return max(helper(vector(nums.begin() + 1, nums.end())),
helper(vector(nums.begin(), nums.end() - 1)));
}
int helper(vector nums) {
if (nums.empty()) return 0;
if (nums.size() == 1) return nums[0];
vector dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp.back();
}
};
Java
public class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(helper(Arrays.copyOfRange(nums, 1, nums.length)),
helper(Arrays.copyOfRange(nums, 0, nums.length - 1)));
}
private int helper(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[nums.length - 1];
}
}
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
return max(self.helper(nums[1:]),
self.helper(nums[:-1]))
def helper(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[-1]JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
return Math.max(this.helper(nums.slice(1)),
this.helper(nums.slice(0, -1)));
}
/**
* @param {number[]} nums
* @return {number}
*/
helper(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[nums.length - 1];
}
}
4. Dynamic Programming Space Optimized Method
Simplify the Bottom-Up approach by keeping track of only the last two states for each scenario, minimizing memory usage while solving for both cases.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int rob(vector& nums) {
vector nums1(nums.begin() + 1, nums.end());
vector nums2(nums.begin(), nums.end() - 1);
return max(nums[0],
max(helper(nums1), helper(nums2)));
}
private:
int helper(vector& nums) {
int rob1 = 0, rob2 = 0;
for (int num : nums) {
int newRob = max(rob1 + num, rob2);
rob1 = rob2;
rob2 = newRob;
}
return rob2;
}
};
Java
public class Solution {
public int rob(int[] nums) {
return Math.max(nums[0],
Math.max(helper(Arrays.copyOfRange(nums, 1, nums.length)),
helper(Arrays.copyOfRange(nums, 0, nums.length - 1))));
}
private int helper(int[] nums) {
int rob1 = 0, rob2 = 0;
for (int num : nums) {
int newRob = Math.max(rob1 + num, rob2);
rob1 = rob2;
rob2 = newRob;
}
return rob2;
}
}
Python
class Solution:
def rob(self, nums: List[int]) -> int:
return max(nums[0], self.helper(nums[1:]),
self.helper(nums[:-1]))
def helper(self, nums):
rob1, rob2 = 0, 0
for num in nums:
newRob = max(rob1 + num, rob2)
rob1 = rob2
rob2 = newRob
return rob2
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
rob(nums) {
return Math.max(
nums[0],
Math.max(
this.helper(nums.slice(1)),
this.helper(nums.slice(0, -1)),
),
);
}
/**
* @param {number[]} nums
* @return {number}
*/
helper(nums) {
let rob1 = 0;
let rob2 = 0;
for (const num of nums) {
const newRob = Math.max(rob1 + num, rob2);
rob1 = rob2;
rob2 = newRob;
}
return rob2;
}
}
