Introduction

House Robber II is a follow-up to the classic House Robber problem.

The difference:

Houses are arranged in a circle.

This means:

First house and last house are adjacent.

Goal:

Find the maximum money that can be robbed without robbingadjacent houses.

Example

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

Explanation:

Cannot rob both first house (2) and last house (2) because they are adjacent.

Best choice:

Rob house 2
Money = 3

Key Observation

Unlike House Robber I:

First and last houses cannot be robbed together.

So divide into two cases.

Case 1

Rob houses[0 ... n-2]

Exclude last house.

Case 2

Rob houses[1 ... n-1]

Exclude first house.

Answer:

max(Case1,Case2)

Approach

Use House Robber I logic twice.

Recurrence:

 dp[i] = max(nums[i] + dp[i-2],dp[i-1])

Dry Run

Input:

 nums = [2,3,2]

Case 1:

[2,3]
Maximum = 3

Case 2:

[3,2]Maximum = 3

Answer:

max(3,3) = 3

Practice

Complexity Analysis

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

Why This Problem is Important

This problem teaches:

  • Circular DP
  • Pick or Skip Pattern
  • State Optimization
  • Case Splitting
  • Interview Follow-up Questions

Common Beginner Mistakes

  • Treating it like House Robber I
  • Robbing first and last houses together
  • Forgetting edge case n = 1
  • Using one DP pass only

Interview Tip

Always explain:

First house and last house cannot coexist.

Therefore:

Run House Robber twice.Exclude first house.
Exclude last house.

Take maximum answer.

Related Questions

  • House Robber
  • Decode Ways
  • Coin Change
  • Climbing Stairs
  • Fibonacci

Final Takeaway

House Robber II extends the classic House Robber problem by introducing a circular arrangement of houses.

The key idea is:

Break circle into two linear problems.

Solve both using House Robber I and take the maximum result. This pattern appears frequently in medium-level Dynamic Programming interviews.