Watch 10 video solutions for House Robber II, a medium level problem involving Array, Dynamic Programming. This walkthrough by take U forward has 484,417 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 money stored in a house. Houses are arranged in a circle, so the first and last houses are neighbors. You cannot rob two adjacent houses. The task is to compute the maximum amount you can rob without triggering alarms.
The circular layout is the only difference from the classic House Robber problem. If you rob the first house, you cannot rob the last. If you rob the last house, you cannot rob the first. This constraint splits the problem into two independent linear subproblems.
Approach 1: Optimization with Memoization (Time: O(n), Space: O(n))
This approach uses dynamic programming with recursion and memoization. The key idea is the same as the original House Robber problem: for each index, decide whether to rob the current house or skip it. If you rob it, you add its value and move to i + 2; if you skip it, move to i + 1. Because the houses form a circle, you evaluate two scenarios: robbing within range [0, n-2] and robbing within range [1, n-1]. Each recursive state is cached to avoid recomputation, giving linear time complexity. This version is useful when you want a top‑down perspective that clearly expresses the decision tree.
Approach 2: Dynamic Programming with Two Passes (Time: O(n), Space: O(1))
This is the optimal iterative solution. Instead of recursion, compute the best robbery plan using two passes over the array. First pass assumes you rob houses from 0 to n-2 (excluding the last). Second pass assumes you rob houses from 1 to n-1 (excluding the first). Each pass runs the classic House Robber DP where you track two values: prev1 (max profit up to previous house) and prev2 (max profit up to the house before that). For every element, compute max(prev1, prev2 + nums[i]). Because only two variables are needed, space remains constant.
The insight is that the circular dependency disappears once you split the problem into these two linear ranges. Each pass solves a standard non‑adjacent selection problem using DP transitions.
Recommended for interviews: The dynamic programming two‑pass approach is what most interviewers expect. It runs in O(n) time with O(1) extra space and clearly demonstrates understanding of circular constraints. The memoization version still shows strong dynamic programming fundamentals and is often easier to reason about initially, but the iterative optimization shows stronger mastery.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Memoization (Top-Down DP) | O(n) | O(n) | When recursion is easier to reason about and you want explicit subproblem caching. |
| Dynamic Programming with Two Passes | O(n) | O(1) | Best practical solution. Handles circular constraint by solving two linear DP cases. |