House Robber II solution and explanation
Infosys
Google
9 more videos on this problem
House Robber II - Dynamic Programming - Leetcode 213NeetCode · 10:40 · 197K views
House Robber II | Recur + Memo | DP Concepts & Qns - 5 | Leetcode-213codestorywithMIK · 15:03 · 48K views
House Robber 2 (LeetCode 213) | Full solution with easy explanation | Diagrams | Study AlgorithmsNikhil Lohia · 10:01 · 24K views
House Robber II | Live Coding with Explanation | Leetcode - 213Algorithms Made Easy · 6:10 · 6K views
Leetcode - House Robber II (Python)Timothy H Chang · 5:33 · 2K views
HOUSE ROBBER II | LEETCODE 213 | PYTHON SOLUTIONCracking FAANG · 8:36 · 1K views
Apple Coding Interview Question - House Robber 2 - LeetCode 213AlgoJS · 6:12 · 1K views
House Robber II | LeetCode 213 | October LeetCode Challenge | Day 14Learn Code Repeat · 9:41 · 691 views
House Robber II Leetcode 213 video | leetcode solutionEasyLeetcode · 9:28 · 474 views
DP 6. House Robber 2 | 1D DP | DP on Subsequencestake U forward · 9:50 · 521K views
The problem
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
Approach overview
Problem 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 1: Dynamic Programming with Two Passes
This approach involves splitting the problem into two scenarios: robbing from house 0 to house n-2, and from house 1 to house n-1. The aim is to apply the linear version of the House Robber problem to each scenario separately and then take the maximum of the two resulting summed values.
def robLinear(nums):
prev1, prev2 = 0, 0
for num in nums:
temp = prev1
prev1 = max(num + prev2, prev1)
prev2 = temp
return prev1
class Solution:
def rob(self, nums):
if len(nums) == 1:
return nums[0]
return max(robLinear(nums[:-1]), robLinear(nums[1:]))
class Solution {
private int robLinear(int[] nums, int start, int end) {
int prev1 = 0, prev2 = 0;
for (int i = start; i < end; i++) {
int temp = prev1;
prev1 = Math.max(nums[i] + prev2, prev1);
prev2 = temp;
}
return prev1;
}
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLinear(nums, 0, n - 1), robLinear(nums, 1, n));
}
}
class Solution {
public:
int robLinear(vector<int>& nums, int start, int end) {
int prev1 = 0, prev2 = 0;
for (int i = start; i < end; i++) {
int temp = prev1;
prev1 = max(nums[i] + prev2, prev1);
prev2 = temp;
}
return prev1;
}
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
return max(robLinear(nums, 0, n - 1), robLinear(nums, 1, n));
}
};
var robLinear = function(nums) {
let prev1 = 0, prev2 = 0;
for (const num of nums) {
let temp = prev1;
prev1 = Math.max(num + prev2, prev1);
prev2 = temp;
}
return prev1;
};
var rob = function(nums) {
if (nums.length === 1) return nums[0];
return Math.max(robLinear(nums.slice(0, nums.length - 1)), robLinear(nums.slice(1)));
};
int robLinear(int* nums, int len) {
if (len == 0) return 0;
if (len == 1) return nums[0];
int prev1 = 0, prev2 = 0;
for (int i = 0; i < len; i++) {
int temp = prev1;
prev1 = (nums[i] + prev2 > prev1) ? nums[i] + prev2 : prev1;
prev2 = temp;
}
return prev1;
}
int rob(int* nums, int numsSize) {
if (numsSize == 1) return nums[0];
return (robLinear(nums, numsSize - 1) > robLinear(nums + 1, numsSize - 1))
? robLinear(nums, numsSize - 1)
: robLinear(nums + 1, numsSize - 1);
}
public class Solution {
private int RobLinear(int[] nums, int start, int end) {
int prev1 = 0, prev2 = 0;
for (int i = start; i < end; i++) {
int temp = prev1;
prev1 = Math.Max(nums[i] + prev2, prev1);
prev2 = temp;
}
return prev1;
}
public int Rob(int[] nums) {
if (nums.Length == 1) return nums[0];
return Math.Max(RobLinear(nums, 0, nums.Length - 1), RobLinear(nums, 1, nums.Length));
}
}This Python solution utilizes a helper function robLinear to handle the linear robbery problem. It then applies this helper to the range excluding first and last houses respectively, returning the greatest result.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Optimization with Memoization
This approach implements a memoized version of the dynamic programming solution to avoid recomputing values. We explore two scenarios of the circle, taking into account the cycles explicitly by caching intermediate results.
class Solution:
def robHelper(self, nums, start, end, memo):
if start >= end:
return 0
if memo[start] >= 0:
return memo[start]
memo[start] = max(nums[start] + self.robHelper(nums, start + 2, end, memo), self.robHelper(nums, start + 1, end, memo))
return memo[start]
def rob(self, nums):
if len(nums) == 1:
return nums[0]
memo1 = [-1] * len(nums)
memo2 = [-1] * len(nums)
return max(self.robHelper(nums, 0, len(nums) - 1, memo1), self.robHelper(nums, 1, len(nums), memo2))
class Solution {
private int[] memo;
private int robHelper(int[] nums, int start, int end) {
if (start >= end) return 0;
if (memo[start] >= 0) return memo[start];
memo[start] = Math.max(nums[start] + robHelper(nums, start + 2, end), robHelper(nums, start + 1, end));
return memo[start];
}
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
memo = new int[nums.length];
Arrays.fill(memo, -1);
int case1 = robHelper(nums, 0, nums.length - 1);
Arrays.fill(memo, -1);
int case2 = robHelper(nums, 1, nums.length);
return Math.max(case1, case2);
}
}
class Solution {
vector<int> memo;
int robHelper(vector<int>& nums, int start, int end) {
if (start >= end) return 0;
if (memo[start] != -1) return memo[start];
memo[start] = max(nums[start] + robHelper(nums, start + 2, end), robHelper(nums, start + 1, end));
return memo[start];
}
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
memo.assign(nums.size(), -1);
int case1 = robHelper(nums, 0, nums.size() - 1);
memo.assign(nums.size(), -1);
int case2 = robHelper(nums, 1, nums.size());
return max(case1, case2);
}
};
var robHelper = function(nums, start, end, memo) {
if (start >= end) return 0;
if (memo[start] !== undefined) return memo[start];
memo[start] = Math.max(nums[start] + robHelper(nums, start + 2, end, memo), robHelper(nums, start + 1, end, memo));
return memo[start];
};
var rob = function(nums) {
if (nums.length === 1) return nums[0];
const memo1 = {};
const memo2 = {};
return Math.max(robHelper(nums, 0, nums.length - 1, memo1), robHelper(nums, 1, nums.length, memo2));
};
#include <string.h>
int memo[101];
int robLinearMemo(int* nums, int start, int end) {
memset(memo, -1, sizeof(memo));
return robHelper(nums, start, end);
}
int robHelper(int* nums, int start, int end) {
if (start >= end) return 0;
if (memo[start] >= 0) return memo[start];
memo[start] = (nums[start] + robHelper(nums, start + 2, end) > robHelper(nums, start + 1, end))
? nums[start] + robHelper(nums, start + 2, end) : robHelper(nums, start + 1, end);
return memo[start];
}
int rob(int* nums, int numsSize) {
if (numsSize == 1) return nums[0];
int case1 = robLinearMemo(nums, 0, numsSize - 1);
int case2 = robLinearMemo(nums, 1, numsSize);
return (case1 > case2) ? case1 : case2;
}
public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();
private int RobHelper(int[] nums, int start, int end) {
if (start >= end) return 0;
if (memo.ContainsKey(start)) return memo[start];
int result = Math.Max(nums[start] + RobHelper(nums, start + 2, end), RobHelper(nums, start + 1, end));
memo[start] = result;
return result;
}
public int Rob(int[] nums) {
if (nums.Length == 1) return nums[0];
memo.Clear();
int case1 = RobHelper(nums, 0, nums.Length - 1);
memo.Clear();
int case2 = RobHelper(nums, 1, nums.Length);
return Math.Max(case1, case2);
}
}This Python solution makes use of a memo array to store intermediate maximums to prevent redundant calculations. The robHelper function recursively determines possible rob outcomes and updates the cache, providing two results depending on whether the first house is considered or not.
Time Complexity: O(n).
Space Complexity: O(n) allocated for memoization.
Approach 3: Dynamic Programming
The circular arrangement means that at most one of the first and last houses can be chosen for theft, so this circular arrangement problem can be reduced to two single-row house problems.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function rob(nums: number[]): number {
const n = nums.length;
if (n === 1) {
return nums[0];
}
const robRange = (l: number, r: number): number => {
let [f, g] = [0, 0];
for (; l <= r; ++l) {
[f, g] = [Math.max(f, g), f + nums[l]];
}
return Math.max(f, g);
};
return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1))
}
func robRange(nums []int, l, r int) int {
f, g := 0, 0
for _, x := range nums[l : r+1] {
f, g = max(f, g), f+x
}
return max(f, g)
}impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 {
return nums[0];
}
let rob_range = |l, r| {
let mut f = [0, 0];
for i in l..r {
f = [f[0].max(f[1]), f[0] + nums[i]];
}
f[0].max(f[1])
};
rob_range(0, n - 1).max(rob_range(1, n))
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Passes | Time Complexity: O(n). |
| Optimization with Memoization | Time Complexity: O(n). |
| Dynamic Programming | – |
Complexity analysis
| 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. |
Frequently asked questions
Is House Robber II easy or hard?
House Robber II is rated Medium difficulty on LeetCode. The dynamic programming transition is straightforward, but recognizing how to handle the circular arrangement of houses is the main challenge.
House Robber II Python/Java solution
Python and Java implementations both follow the same DP logic: compute the best robbery value for ranges [0..n-2] and [1..n-1]. Each iteration updates two variables representing previous optimal values. This keeps the solution O(n) time and O(1) space.
How to solve House Robber II in O(n)?
Split the circular problem into two linear robbery problems: exclude the last house or exclude the first house. Run the classic House Robber dynamic programming transition max(prev1, prev2 + nums[i]) for each range. Compute both results and return the larger value.
What is the best approach for House Robber II?
The best approach is dynamic programming with two passes. Because the houses form a circle, you cannot rob both the first and last house. Solve two linear cases: houses [0..n-2] and houses [1..n-1], then take the maximum result. This runs in O(n) time and O(1) space.
Is House Robber II asked at Google/Amazon/Meta?
House Robber variants frequently appear in interviews at companies like Amazon, Google, and Meta because they test dynamic programming fundamentals. Interviewers expect candidates to recognize the circular constraint and reduce it to two linear DP problems.
What data structure is used in House Robber II?
The solution primarily uses arrays and dynamic programming state variables. In the optimized version, only two variables are needed to track the previous DP states, reducing space complexity to constant space.
What is the time complexity of House Robber II?
The optimal solution runs in O(n) time because each house is processed a constant number of times. Space complexity can be reduced to O(1) by storing only the last two DP states instead of a full array.