Skip to main content

213. House Robber II

medium

Houses arranged in a circle — the first and last touch. Rob a non-adjacent subset to maximize loot. Reduces to two linear House Robber runs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The circle constraint only matters because the first and last house are now adjacent.

Hint 2

Either you include the first house and skip the last, or skip the first and consider the last. Two independent linear problems.

Hint 3

Run the standard House Robber DP twice — once on nums[0..n-2] and once on nums[1..n-1] — and take the max.

Solution approach

Reveal approach

Reduce to two runs of the linear House Robber subroutine. Define rob_linear(arr) that maintains two rolling values: prev (max if previous was robbed) and prev2 (max if it wasn't); at each i compute curr = max(prev, prev2 + arr[i]), then shift. For the circular variant, run rob_linear on nums[0..n-2] (excludes the last house, so robbing the first is safe) and rob_linear on nums[1..n-1] (excludes the first house, so robbing the last is safe). Return the max of the two. Handle n = 1 as an edge case (return nums[0]).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

Practice these live with InterviewChamp.AI

Drill House Robber II and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →