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
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 ); } }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.