Skip to main content
Talentd

House Robber II - Solution & Explanation

MediumArrayDynamic Programming16 min readAsked at: Amazon, Microsoft, Apple +16
Practice this problem

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 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 <= 100
  • 0 <= 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.

This C solution defines a helper function robLinear for the simpler linear version of the House Robber problem, then uses this to calculate the maximum rob amount in two scenarios: excluding the first and last house respectively. The final result is the maximum of these two computed values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor →

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.

The C solution sets up a memo array for memoization to store calculated maximums for each house start index. It runs the helper function robHelper which recursively looks for the maximum stealing options, caching results for efficiency. It applies this to the scenarios that exclude the first and last house respectively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Two Passes

Time Complexity: O(n).
Space Complexity: O(1).

Optimization with Memoization

Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 PassesO(n)O(1)Best practical solution. Handles circular constraint by solving two linear DP cases.

Video Solution

DP 6. House Robber 2 | 1D DP | DP on Subsequences • take U forward • 521,124 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice House Robber II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Path

Next

House Robber