Watch 10 video solutions for House Robber II, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 377,804 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000Problem Overview: You are given an array where each element represents the money inside a house. Houses are arranged in a circle, so the first and last houses are adjacent. If you rob two adjacent houses, the alarm triggers. The goal is to compute the maximum money you can steal without robbing neighboring houses.
Approach 1: Dynamic Programming with Two Passes (O(n) time, O(1) space)
The circular layout is the only twist compared to the original House Robber problem. Because the first and last houses are neighbors, you cannot rob both. Break the problem into two linear cases: rob houses [0..n-2] or rob houses [1..n-1]. Each case becomes the classic linear DP problem where you track the best profit while iterating through the array. At every index, decide whether to rob the current house (prev2 + nums[i]) or skip it (prev1). Compute both scenarios and take the maximum. This approach runs in O(n) time and uses O(1) extra space because it only keeps the last two states.
This solution works well because the circular dependency disappears once you exclude either the first or the last house. The logic becomes identical to the standard robber DP pattern commonly seen in dynamic programming problems on arrays.
Approach 2: Optimization with Memoization (O(n) time, O(n) space)
This version uses top-down recursion with memoization. Define a function dfs(i) that returns the maximum money you can rob starting from index i. For each house, choose between skipping it (dfs(i+1)) or robbing it (nums[i] + dfs(i+2)). Cache results in a memo array to avoid recomputation. As with the previous approach, solve two subproblems to handle the circular layout: one excluding the last house and one excluding the first.
Memoization makes the recursive solution efficient because each state is computed once. The recursion tree collapses into O(n) states, giving O(n) time complexity. The memo table and recursion stack require O(n) space. This style is useful when you prefer expressing the recurrence relation directly or when converting recursive logic into bottom‑up DP later.
Recommended for interviews: The two-pass dynamic programming approach is what most interviewers expect. It shows you recognize the circular constraint and reduce it to two linear robber problems. Mentioning the memoized recursion demonstrates understanding of the DP recurrence, but the constant-space iterative solution shows stronger optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Two Passes | O(n) | O(1) | Best general solution. Handles the circular constraint by splitting into two linear robber cases. |
| Memoization (Top-Down DP) | O(n) | O(n) | Useful when deriving the recurrence relation or converting recursive logic into dynamic programming. |