House Robber II
MedPrompt
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.
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: 3
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
Use recursion to explore all possible combinations of houses that can be robbed without alerting the police, considering the circular arrangement.
Algorithm
- If array is empty, return 0
- If array has only one element, return that element
- For each position:
- Consider two subarrays: one excluding the last element and another excluding the first element
- For each subarray, recursively calculate:
- Maximum money if current house is robbed (skip next house)
- Maximum money if current house is skipped (consider next house)
- Return maximum of the two subarray results
Walkthrough
This approach uses recursion to solve the problem by considering two cases for each house - either rob it or skip it. Since the houses are arranged in a circle, we need to handle the first and last house separately to avoid robbing adjacent houses.
class Solution { public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; return Math.max( robHelper(nums, 0, nums.length - 2), robHelper(nums, 1, nums.length - 1) ); } private int robHelper(int[] nums, int start, int end) { if (start > end) return 0; if (start == end) return nums[start]; return Math.max( nums[start] + robHelper(nums, start + 2, end), robHelper(nums, start + 1, end) ); }}Complexity
Time
O(2^n) - where n is the length of the array, as we make two recursive calls for each element
Space
O(n) - due to the recursive call stack
Trade-offs
Pros
Simple and intuitive approach
Easy to understand and implement
Cons
Exponential time complexity makes it inefficient for larger inputs
Redundant calculations of same subproblems
Can cause stack overflow for large inputs
Optimize the recursive solution by storing previously calculated results in a memoization array to avoid redundant calculations.
Algorithm
- If array is empty, return 0
- If array has only one element, return that element
- Create two memoization maps for two subarrays
- For each position:
- Check if result exists in memo
- If not, calculate and store:
- Maximum money if current house is robbed
- Maximum money if current house is skipped
- Return maximum of the two subarray results
Walkthrough
This approach improves the recursive solution by using memoization to store the results of subproblems. We use a HashMap to store the results of each subproblem indexed by the position.
class Solution { public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; Map<Integer, Integer> memo1 = new HashMap<>(); Map<Integer, Integer> memo2 = new HashMap<>(); return Math.max( robHelper(nums, 0, nums.length - 2, memo1), robHelper(nums, 1, nums.length - 1, memo2) ); } private int robHelper(int[] nums, int start, int end, Map<Integer, Integer> memo) { if (start > end) return 0; if (start == end) return nums[start]; if (memo.containsKey(start)) return memo.get(start); int result = Math.max( nums[start] + robHelper(nums, start + 2, end, memo), robHelper(nums, start + 1, end, memo) ); memo.put(start, result); return result; }}Complexity
Time
O(n) - where n is the length of the array, as each subproblem is solved only once
Space
O(n) - for the memoization map and recursive call stack
Trade-offs
Pros
Reduces time complexity by avoiding redundant calculations
Uses memory to store intermediate results
Still maintains the recursive structure
Cons
Still uses recursive calls which can lead to stack overflow
Requires additional space for memoization
Not as efficient as iterative approach
Use an iterative approach with dynamic programming to calculate the maximum amount that can be robbed, considering the circular arrangement of houses.
Algorithm
- Handle base cases for arrays of length 0, 1, and 2
- For the main array, consider two subarrays:
- One excluding the last house
- One excluding the first house
- For each subarray:
- Maintain three variables for dp[i-2], dp[i-1], and current
- For each house i:
- Calculate maximum of (previous house, current house + house two steps back)
- Update the variables
- Return maximum of the two subarray results
Walkthrough
This approach uses dynamic programming with iteration to solve the problem. We handle the circular arrangement by running the algorithm twice - once excluding the first house and once excluding the last house. For each subarray, we maintain a dp array where dp[i] represents the maximum amount that can be robbed up to house i.
class Solution { public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; if (nums.length == 2) return Math.max(nums[0], nums[1]); return Math.max( robRange(nums, 0, nums.length - 2), // Exclude last house robRange(nums, 1, nums.length - 1) // Exclude first house ); } private int robRange(int[] nums, int start, int end) { int prev2 = 0; // dp[i-2] int prev1 = 0; // dp[i-1] int current = 0; for (int i = start; i <= end; i++) { current = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = current; } return current; }}Complexity
Time
O(n) - where n is the length of the array, as we iterate through the array twice
Space
O(1) - only uses three variables regardless of input size
Trade-offs
Pros
Most efficient solution with linear time complexity
No recursion, so no stack overflow risk
Uses constant extra space
Faster execution compared to recursive approaches
Cons
Slightly more complex to understand than recursive approach
Requires careful handling of edge cases
Need to run the algorithm twice for the two subarrays
Solutions
Solution
class Solution { public int rob ( int [] nums ) { int n = nums . length ; if ( n == 1 ) { return nums [ 0 ]; } return Math . max ( rob ( nums , 0 , n - 2 ), rob ( nums , 1 , n - 1 )); } private int rob ( int [] nums , int l , int r ) { int f = 0 , g = 0 ; for (; l <= r ; ++ l ) { int ff = Math . max ( f , g ); g = f + nums [ l ]; f = ff ; } return Math . max ( f , g ); } }class Solution {public: int rob(vector<int> &nums) { int n = nums.size(); if (n == 1) { return nums[0]; } return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1)); } int robRange(vector<int> &nums, int l, int r) { int f = 0, g = 0; for (; l <= r; ++l) { int ff = max(f, g); g = f + nums[l]; f = ff; } return max(f, g); }};class Solution : def rob ( self , nums : List [ int ]) -> int : def robRange ( nums , l , r ): # re-use LC-198 solution not_rob , rob = 0 , nums [ l ] for num in nums [ l + 1 : r + 1 ]: # to include 'r' not_rob , rob = rob , max ( num + not_rob , rob ) return rob n = len ( nums ) if n == 1 : return nums [ 0 ] s1 , s2 = robRange ( nums , 0 , n - 2 ), robRange ( nums , 1 , n - 1 ) # inclusive return max ( s1 , s2 ) ############ class Solution : def rob ( self , nums : List [ int ]) -> int : def _rob ( nums ): f = g = 0 for x in nums : f , g = max ( f , g ), f + x return max ( f , g ) if len ( nums ) == 1 : return nums [ 0 ] return max ( _rob ( nums [ 1 :]), _rob ( nums [: - 1 ]))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.