214. House Robber II
🔗 LeetCode Problem: 213. House Robber II
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, 1D DP
Problem Statement
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 the same security system as the house robber I problem, which means adjacent houses have security systems 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 <= 100
- 0 <= nums[i] <= 1000
🌳 Visual Understanding - Using [2, 3, 2]
The Problem We're Solving:
Houses arranged in a CIRCLE:
Linear Street (House Robber I):
[2, 3, 2]
🏠 🏠 🏠
H0-H1-H2
Circular Street (House Robber II):
H0($2)
/ \
H2($2) H1($3)
\ /
---
NOW: H0 and H2 are NEIGHBORS! 🎯
Can't rob both H0 and H2 (they're adjacent in circle!)
The NEW Constraint:
Houses: [2, 3, 2]
House Robber I (Linear):
Valid plans:
- Rob H0, H2: $2 + $2 = $4 ✓
- Rob H1: $3 ✓
- Rob H0: $2 ✓
- Rob H2: $2 ✓
Maximum: $4 from [H0, H2]
House Robber II (Circular):
H0 and H2 are NEIGHBORS NOW!
Invalid plans:
- Rob H0, H2: $2 + $2 = $4 ✗ (adjacent in circle!)
Valid plans:
- Rob H1: $3 ✓ MAXIMUM!
- Rob H0: $2 ✓
- Rob H2: $2 ✓
Maximum: $3 from [H1] only
The circle changes everything! 🎯
Better Example: [1, 2, 3, 1]
Circular arrangement:
H0($1)
/ \
H3($1) H1($2)
\ /
H2($3)
Adjacent pairs:
H0 ↔ H1 (neighbors)
H1 ↔ H2 (neighbors)
H2 ↔ H3 (neighbors)
H3 ↔ H0 (neighbors in circle!) 🔄
CANNOT rob both H0 AND H3!
This is the key constraint!
Finding All Valid Plans:
Houses: [1, 2, 3, 1]
Plan 1: Rob H0 and H2
Money: $1 + $3 = $4 ✓
Check adjacency:
- H0 not adjacent to H2? YES ✓
- But can we rob both given H0↔H3 adjacency?
- If rob H0, skip H1 and H3
- If rob H2, already skipped H3
Valid! Money: $4 ✓
Plan 2: Rob H1 and H3
Money: $2 + $1 = $3 ✓
Valid? H1↔H3 not adjacent ✓
Plan 3: Just H2
Money: $3 ✓
Maximum: $4 from [H0, H2] ✓
🧠 The AHA Moment - The Clever Trick!
The Key Insight:
The problem: First and last houses are neighbors!
BRILLIANT OBSERVATION:
We can't rob BOTH first and last house!
So we have TWO scenarios:
Scenario 1: Rob first house
→ MUST skip last house
→ Rob from houses [0, 1, 2, ..., n-2]
→ Don't even consider last house!
Scenario 2: Skip first house
→ CAN rob last house
→ Rob from houses [1, 2, 3, ..., n-1]
→ Don't even consider first house!
Take maximum of both scenarios! 🎯
Visual Explanation:
Original circle: [1, 2, 3, 1]
H0($1)
/ \
H3($1) H1($2)
\ /
H2($3)
Break the circle into TWO linear problems:
Scenario 1: Include first, exclude last
[1, 2, 3] (houses 0, 1, 2)
🏠 🏠 🏠
H0 H1 H2
Solve as House Robber I: max = $4 (rob H0, H2)
Scenario 2: Exclude first, include last
[2, 3, 1] (houses 1, 2, 3)
🏠 🏠 🏠
H1 H2 H3
Solve as House Robber I: max = $3 (rob H2)
Answer = max($4, $3) = $4 ✓
Why This Works:
CLAIM: At least ONE of these scenarios gives optimal answer
PROOF:
In optimal solution, we either:
Case A: Rob first house
→ Can't rob last (adjacent)
→ Scenario 1 covers this!
Case B: Don't rob first house
→ Can rob last or not
→ Scenario 2 covers this!
Since scenarios cover all cases,
one of them MUST be optimal! 🎯
BEAUTIFUL REDUCTION:
Circular problem → Two linear problems!
Reuse House Robber I solution twice!
Edge Case - Single House:
nums = [5]
If we use the two-scenario approach:
Scenario 1: [5] excluding last → [] empty!
Scenario 2: [] excluding first → [] empty!
Both empty arrays! ⚠️
SOLUTION:
If n == 1, just return nums[0]
Special case needed!
🟢 Approach: Two Linear Subproblems (Elegant Solution)
📐 Function Definition
Function Signature:
int rob(int[] nums)
int robLinear(int[] nums, int start, int end)
What it represents:
Input Parameter nums:
- Array of money in circular houses
- Example: nums = [1, 2, 3, 1]
Input Parameters start and end:
- Range of houses to consider
- Example: robLinear(nums, 0, n-2) = houses 0 to n-2
- Example: robLinear(nums, 1, n-1) = houses 1 to n-1
Return Value (int): - Maximum money robbing houses in range [start, end]
Purpose: - Solve two linear House Robber problems - Take maximum of both
Key Understanding:
rob(nums) asks:
"Max money from circular houses?"
Break into two cases:
Case 1: robLinear(nums, 0, n-2)
"Include first house, exclude last"
Case 2: robLinear(nums, 1, n-1)
"Exclude first house, include last"
Answer = max(case 1, case 2)
💡 Intuition
Think of it as breaking the circle into two paths:
Circular problem feels complicated...
But wait! We can't rob BOTH ends!
So create TWO linear problems:
Path 1: Start from first house
H0($1)
/
H3 H1($2)
\
H2($3)
Can rob: H0, H1, H2 (not H3!)
Linear: [1, 2, 3]
Solve: Rob H0 and H2 → $4
Path 2: Start from second house
H0
/
H3($1) H1($2)
\ /
H2($3)
Can rob: H1, H2, H3 (not H0!)
Linear: [2, 3, 1]
Solve: Rob H2 → $3
Take max($4, $3) = $4 ✓
Simple and elegant! 🎯
📝 Implementation
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// Edge case: single house
if (n == 1) return nums[0];
// Edge case: two houses
if (n == 2) return Math.max(nums[0], nums[1]);
// Scenario 1: Rob houses 0 to n-2 (include first, exclude last)
int scenario1 = robLinear(nums, 0, n - 2);
// Scenario 2: Rob houses 1 to n-1 (exclude first, include last)
int scenario2 = robLinear(nums, 1, n - 1);
// Take maximum of both scenarios
return Math.max(scenario1, scenario2);
}
// House Robber I solution (linear houses)
private int robLinear(int[] nums, int start, int end) {
int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]
for (int i = start; i <= end; i++) {
int current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
🔍 Detailed Dry Run: nums = [1, 2, 3, 1]
nums = [1, 2, 3, 1]
n = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SCENARIO 1: Include first, exclude last
Houses: [1, 2, 3] (indices 0, 1, 2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
robLinear(nums, 0, 2):
Initialize:
prev2 = 0
prev1 = 0
i = 0 (value = 1):
current = max(prev1, prev2 + nums[0])
= max(0, 0 + 1)
= 1
prev2 = 0, prev1 = 1
i = 1 (value = 2):
current = max(prev1, prev2 + nums[1])
= max(1, 0 + 2)
= 2
prev2 = 1, prev1 = 2
i = 2 (value = 3):
current = max(prev1, prev2 + nums[2])
= max(2, 1 + 3)
= max(2, 4)
= 4 ✓
prev2 = 2, prev1 = 4
scenario1 = 4
Plan: Rob H0 ($1) and H2 ($3) → $4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SCENARIO 2: Exclude first, include last
Houses: [2, 3, 1] (indices 1, 2, 3)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
robLinear(nums, 1, 3):
Initialize:
prev2 = 0
prev1 = 0
i = 1 (value = 2):
current = max(prev1, prev2 + nums[1])
= max(0, 0 + 2)
= 2
prev2 = 0, prev1 = 2
i = 2 (value = 3):
current = max(prev1, prev2 + nums[2])
= max(2, 0 + 3)
= 3
prev2 = 2, prev1 = 3
i = 3 (value = 1):
current = max(prev1, prev2 + nums[3])
= max(3, 2 + 1)
= max(3, 3)
= 3
prev2 = 3, prev1 = 3
scenario2 = 3
Plan: Rob H2 ($3) → $3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL ANSWER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
result = max(scenario1, scenario2)
= max(4, 3)
= 4 ✓
Best plan: Scenario 1 (Rob H0 and H2)
Houses robbed: 0 and 2
Money: $1 + $3 = $4 ✓
Visual Comparison:
Original Circle: [1, 2, 3, 1]
H0($1)
/ \
H3($1) H1($2)
\ /
H2($3)
Scenario 1: [1, 2, 3] Scenario 2: [2, 3, 1]
🏠 🏠 🏠 🏠 🏠 🏠
H0 H1 H2 H1 H2 H3
✓ ✗ ✓ → $4 ✗ ✓ ✗ → $3
Better: Scenario 1 with $4! ✓
📊 Complexity Analysis
Time Complexity: O(n)
Scenario 1: O(n-1) = O(n)
Scenario 2: O(n-1) = O(n)
Total: O(n) + O(n) = O(n) ✓
Space Complexity: O(1)
Using space-optimized House Robber I
Only two variables per scenario
Total: O(1) ✓
🎯 Pattern Recognition - Breaking Circular Constraints
Core Pattern: Circular → Multiple Linear
When circular constraint appears:
→ Break into multiple linear subproblems
→ Cover all cases with subproblems
→ Take optimal across all cases
For House Robber II:
Circular: First and last are neighbors
Break into:
Case 1: Include first → Exclude last
Case 2: Exclude first → Can include last
Answer = max(case 1, case 2)
Similar Problems:
- Paint House (circular arrangement)
- Best Time to Buy/Sell Stock (wraparound)
- Cutting a Rod (circular cuts)
The Key Question to Ask:
"What makes this problem circular?"
→ First and last are connected
"Can we break the circle?"
→ Yes! Can't rob both endpoints!
"How many scenarios needed?"
→ Two: with first, without first
"Do scenarios cover all cases?"
→ Yes! Every solution fits one scenario!
This thinking works for many circular problems! 🎯
⚠️ Important Edge Cases to Test
nums = [1] // Expected: 1 (single house)
nums = [1,2] // Expected: 2 (two houses, take max)
nums = [2,3,2] // Expected: 3 (can't rob both ends)
nums = [1,2,3,1] // Expected: 4 (rob 0 and 2)
nums = [1,2,3] // Expected: 3 (rob last)
nums = [5,1,1,5] // Expected: 5 (rob one end)
nums = [1,1,1,2] // Expected: 3 (skip first or last)
nums = [2,1,1,2] // Expected: 3 (rob both ends impossible)
nums = [1,2,1,1] // Expected: 3 (rob second and fourth)
nums = [4,1,2,7,5,3,1] // Expected: 14 (multiple houses)
📝 Quick Revision Notes
🎯 Core Concept
Problem: Rob circular houses for max money without robbing adjacent houses.
Key Insight: First and last houses are neighbors! Can't rob both! Break into two linear subproblems.
Approach: - Two Linear Subproblems → O(n), O(1) space ⭐
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int rob(int[] a) {
if (a.length < 2) {
return a[0];
}
if (a.length < 3) {
return Math.max(a[0], a[1]);
}
// // Approach 1 - recursive
// return Math.max(recursive(0, a.length - 1, a), recursive(1, a.length, a));
// // Approach 2 - top down
// int[] memo1 = new int[a.length];
// Arrays.fill(memo1, -1);
// int[] memo2 = new int[a.length];
// Arrays.fill(memo2, -1);
// return Math.max(topDown(0, a.length - 1, a, memo1), topDown(1, a.length, a,
// memo2));
// Approach 3 - bottom up
return Math.max(bottomUp(a, 0, a.length - 2), bottomUp(a, 1, a.length - 1));
}
private int bottomUp(int[] a, int start, int end) {
int n = a.length - 1; // maintain size one less
int[] dp = new int[n];
// base cases
dp[0] = a[start];
dp[1] = Math.max(a[start], a[start + 1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(a[start + i] + dp[i - 2], dp[i - 1]);
}
return dp[n - 1];
}
private int topDown(int index, int end, int[] a, int[] memo) {
if (index >= end) {
return 0;
}
if (memo[index] != -1) {
return memo[index];
}
int robHouse = a[index] + topDown(index + 2, end, a, memo);
int skipHouse = topDown(index + 1, end, a, memo);
return memo[index] = Math.max(skipHouse, robHouse);
}
private int recursive(int index, int end, int[] a) {
if (index >= end) {
return 0;
}
int robHouse = a[index] + recursive(index + 2, end, a);
int skipHouse = recursive(index + 1, end, a);
return Math.max(skipHouse, robHouse);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.rob(new int[] { 2, 3, 2 }) == 3);
System.out.println(s.rob(new int[] { 1, 2, 3, 1 }) == 4);
System.out.println(s.rob(new int[] { 1, 2, 3 }) == 3);
System.out.println(s.rob(new int[] { 1, 2, 1, 1 }) == 3);
}
}
// Best Solution!
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
return Math.max(
robLinear(nums, 0, n - 2), // Include first, exclude last
robLinear(nums, 1, n - 1) // Exclude first, include last
);
}
private int robLinear(int[] nums, int start, int end) {
int prev2 = 0, prev1 = 0;
for (int i = start; i <= end; i++) {
int curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
🔑 Key Insights
The Circular Problem:
H0($1)
/ \
H3($1) H1($2)
\ /
H2($3)
First (H0) and Last (H3) are NEIGHBORS!
Can't rob both!
The Beautiful Reduction:
Can't rob both H0 and H(n-1)
So we have TWO cases:
Case 1: Rob H0 → Can't rob H(n-1)
Solve: [H0, H1, ..., H(n-2)]
Case 2: Don't rob H0 → Can rob H(n-1)
Solve: [H1, H2, ..., H(n-1)]
Take maximum! ✓
Circular → Two Linear! 🎯
Why This Covers Everything:
Any optimal solution either:
- Robs first house (Case 1 covers this)
- Doesn't rob first house (Case 2 covers this)
One of these MUST be optimal!
No other cases possible!
Edge Cases Matter:
n = 1: Just return nums[0]
(Can't create two subproblems!)
n = 2: Return max(nums[0], nums[1])
(They're adjacent, pick one!)
Always handle edge cases first!
🎪 Memory Aid
"Circle? Can't rob both ends!"
"Break circle → Two paths!"
"With first OR without first!"
"Take maximum of both!" ✨
⚠️ Common Mistakes
- ❌ Forgetting edge case n=1 (causes empty array!)
- ❌ Not handling n=2 separately
- ❌ Including both first AND last in same scenario
- ❌ Using wrong indices (0 to n-1 instead of 0 to n-2)
- ❌ Not reusing House Robber I solution
✅ Interview Talking Points
"This is House Robber with circular constraint.
Key insight:
First and last houses are neighbors
Can't rob both!
Approach:
Break into TWO linear subproblems:
1. Include first house
→ Must exclude last house
→ Solve for houses [0 to n-2]
2. Exclude first house
→ Can include last house
→ Solve for houses [1 to n-1]
Take maximum of both scenarios
Why this works:
Any optimal solution either robs first house
or doesn't rob first house
These two cases cover everything!
Implementation:
Reuse House Robber I solution twice
Space-optimized: O(1) per scenario
Edge cases:
- n=1: return nums[0]
- n=2: return max(nums[0], nums[1])
Complexity: O(n) time, O(1) space
Beautiful reduction! 🎯"
🎉 Congratulations!
You've mastered House Robber II - circular constraint variant!
What You Learned:
✅ Circular Constraints - First and last connected
✅ Breaking Circles - Multiple linear subproblems
✅ Case Coverage - Ensuring all scenarios covered
✅ Reduction Technique - Hard → Easy subproblems
✅ Reusing Solutions - Apply House Robber I twice
✅ Edge Case Handling - n=1 and n=2 special cases
The Beautiful Pattern:
House Robber I (213):
Linear houses
Rob or skip each house
O(n) time, O(1) space
House Robber II (214):
Circular houses
Can't rob both ends
Reduction:
→ Two linear subproblems
→ Reuse House Robber I
→ Take maximum
O(n) time, O(1) space
Same complexity, elegant solution! 🎯
You've now mastered 5 awesome DP problems (210-214)! 🚀✨