Skip to content

Practice House Robber II

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#213
LeetCode Problem

House Robber II

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.

Source: House Robber II on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [2,3,2]
Output
3

# Example 2

Input
nums = [1,2,3,1]
Output
4

# Example 3

Input
nums = [1,2,3]
Output
3

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 1000

How to solve House Robber II

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

The only new rule on a circle is that the first and last houses cannot both be robbed, so the problem splits into two linear House Robber instances, one dropping the last house and one dropping the first, and the answer is the better of the two.

Why brute force is not enough

Enumerating every subset of houses and discarding those with adjacent picks, including the wraparound pair, is O(2^n), about 10^30 subsets for n up to 100. A memoized recursion that also tracks whether house 0 was taken works but doubles the state for no benefit.

Approach

  1. If there is a single house, return its value, since excluding either end would leave nothing.
  2. Write the linear routine: scan the houses keeping the best total for the prefix so far and the best total for the prefix one shorter; for each house the new best is the larger of skipping it or adding its value to the total from two houses back.
  3. Run that routine on indices 0 through n-2, which models never robbing the last house so the ends cannot clash.
  4. Run it again on indices 1 through n-1, modeling never robbing the first house.
  5. Return the larger result; every valid circular selection omits at least one end house, so one of the two runs has considered it.

Walkthrough of Example 2

nums = [1,2,3,1] → 4

  1. n is 4, so solve the linear problems on [1,2,3] (dropping the last house) and [2,3,1] (dropping the first).
  2. On [1,2,3]: after the first house the best is 1; after the second it is max(1, 2) = 2; after the third it is max(2, 1 + 3) = 4.
  3. On [2,3,1]: the best is 2, then max(2, 3) = 3, then max(3, 2 + 1) = 3.
  4. The answer is max(4, 3) = 4, from robbing the houses worth 1 and 3 at indices 0 and 2.

Time and space

Time O(n) · Space O(1). n is nums.length; each of the two linear passes visits every house once and keeps only two rolling totals, so no table of subproblem answers is stored.

Interview pitfalls

  • Forgetting n equals 1: both reduced ranges are empty and return 0 instead of the lone house's value.
  • Off-by-one in the two ranges, such as running one pass on indices 0 through n-1, which quietly reintroduces the wraparound conflict.
  • Reusing rolling variables across the two runs without resetting them, contaminating the second pass.
  • Trying to patch the full-circle linear answer afterward instead of building the exclusion into the ranges; there is no simple correction.

Follow-up questions interviewers ask

  • How would you return the actual set of houses robbed, not just the total?
  • If the houses formed a tree instead of a circle, how does the recurrence change?
  • What if you must rob at least one of any three consecutive houses?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to House Robber II.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.