CMD Guide
Home › DSA › Company Practice

medium House Robber II

Problem Statement

You are given an array representing the amount of money each house has. This array models a circle of houses, meaning that the first and last houses are adjacent. You are tasked with figuring out the maximum amount of money you can rob without alerting the neighbors.

The rule is: if you rob one house, you cannot rob its adjacent houses.

Example Generation

Example 1:

Example 2:

Example 3:

Constraints:

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — House Robber II medium

0. Pattern family

Family: Circular DP / house robber variants

1. Why / judgment (K3)

Houses in a circle: first and last adjacent. Reduce to max(rob linear[0..n-2], rob linear[1..n-1]).

2. Worked complexity / derivation (K11)

Two linear HR passes O(n) time O(1) space each. Full circular DP same asymptotic.

3. Pattern + recognition + when-NOT (K12)

Name: CIRCULAR HOUSE ROBBER (two linear ranges)

Recognition: max non-adjacent sum on circle / cycle constraint on ends.

When-NOT: Tree houses → House Robber III. No circle → classic HR I. Must rob k houses → different.

4. Edge hand-run (K13)

[2,3,2] → 3. [1,2,3,1] → 4 (1+3). Single house → that value. Two houses → max.

5. Interviewer follow-ups & drills

Q1. Why not one DP with wrap flag?
Model answer: Two ranges simpler and same O(n).

Q2. Empty?
Model answer: 0.

Q3. All equal?
Model answer: Take every other; circle forces drop one end group.

✅ Solution House Robber II

Problem Statement

You are given an array representing the amount of money each house has. This array models a circle of houses, meaning that the first and last houses are adjacent. You are tasked with figuring out the maximum amount of money you can rob without alerting the neighbors.

The rule is: if you rob one house, you cannot rob its adjacent houses.

Examples

Example 1:

  • Input: [4, 2, 3, 1]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 4 + 3 = 7.

Example 2:

  • Input: [5, 1, 2, 5]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 5 + 2 = 7.

Example 3:

  • Input: [1, 2, 3, 4, 5]
  • Expected Output: 8
  • Justification: Rob the 3rd and 5th house, which gives 3 + 5 = 8.

Constraints:

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

Solution

The core idea of our algorithm is to split the circular house problem into two simpler linear problems and then solve each linear problem using a dynamic programming approach. Since the first and last houses in the circle are adjacent, we can't rob them both. Thus, we consider two scenarios: robbing houses excluding the first one and robbing houses excluding the last one. For each scenario, we use a helper function that returns the maximum amount we can rob. This helper function utilizes dynamic programming to keep track of the cumulative robbery amounts, ensuring that no two consecutive houses are robbed. Finally, our solution is the maximum of the two scenarios.

  1. Edge Cases Handling: Begin by checking for edge cases:

    • If the input array is null or has a length of 0, return 0 since there are no houses to rob.
    • If there's only one house, return its value.
    • If there are two houses, return the maximum value of the two houses.

  2. Two Scenarios Handling: Due to the circular structure, handle two scenarios:

    • Exclude the first house and compute for the rest.
    • Exclude the last house and compute for the others.

    Use a helper function to compute the maximum for each scenario.

  3. Simple Robber Helper Function: This function calculates the maximum robbing amount for a linear set of houses using dynamic programming:

    • Maintain two variables, prevMax and currMax, to keep track of the max amount robbed up to the previous and current house, respectively.
    • Iterate through each house in the given range (based on the scenario). At each house, decide whether to rob it (in which case you can't rob the previous house) or skip it.
    • For each house, update currMax based on whether robbing the current house results in a larger amount than skipping it.

  4. Return the Maximum: The main function concludes by returning the maximum value from the two scenarios.

Algorithm Walkthrough

Using the input [4, 2, 3, 1]:

  1. Check for edge cases. Since the array has more than two houses, move to the next step.

  2. Calculate the maximum amount that can be robbed for the two scenarios:

    a. For the scenario excluding the last house (consider houses from index 0 to 2):

    • Start with prevMax = 0 and currMax = 0.
    • For the first house (value 4), currMax becomes 4.
    • For the second house (value 2), currMax remains 4 (because 4 > 2 + 0).
    • For the third house (value 3), currMax becomes 7 (because 4 + 3 > 4). So, for this scenario, the maximum is 7.

    b. For the scenario excluding the first house (consider houses from index 1 to 3):

    • Start with prevMax = 0 and currMax = 0.
    • For the second house (value 2), currMax becomes 2.
    • For the third house (value 3), currMax becomes 3 (because 3 > 2).
    • For the fourth house (value 1), currMax remains 3 (because 3 > 1 + 2). So, for this scenario, the maximum is 3.

  3. The main function then returns the maximum of the two scenarios, which is 7 in this case.

Code

java
public class Solution {

  // Main rob function that handles the circle scenario.
  public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    if (nums.length == 2) return Math.max(nums[0], nums[1]);

    // Compare the result excluding the first or the last house.
    return Math.max(
      robSimple(nums, 0, nums.length - 2),
      robSimple(nums, 1, nums.length - 1)
    );
  }

  // The simple rob function that doesn't consider the circle scenario.
  private int robSimple(int[] nums, int start, int end) {
    int prevMax = 0;
    int currMax = 0;
    for (int i = start; i <= end; i++) {
      int temp = currMax;
      currMax = Math.max(prevMax + nums[i], currMax);
      prevMax = temp;
    }
    return currMax;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.rob(new int[] { 4, 2, 3, 1 })); // Expected 7
    System.out.println(solution.rob(new int[] { 5, 1, 2, 5 })); // Expected 7
    System.out.println(solution.rob(new int[] { 1, 2, 3, 4, 5 })); // Expected 8
  }
}

Complexity Analysis

Time Complexity: We are solving the house robber problem twice (once excluding the first house and once excluding the last house). Each run of the house robber problem has a time complexity of (O(n)), where (n) is the number of houses. Thus, our overall time complexity is (O(n)).

Space Complexity: We use a constant amount of space to store our previous and current max values. Hence, the space complexity is (O(1)).

🎯 STRICT STANDOUT — Solution House Robber II

0. Pattern family

Family: Circular DP two linear HR

1. Why / judgment (K3)

Implement rob_linear twice on ranges excluding first / excluding last; take max. Base n=1 careful.

2. Worked complexity / derivation (K11)

O(n) time O(1) space (rolling prev2).

3. Pattern + recognition + when-NOT (K12)

Name: CIRCULAR HOUSE ROBBER

Recognition: max non-adjacent on circle.

When-NOT: HR on tree/graph.

4. Edge hand-run (K13)

n=1 return nums[0] before splitting ranges. n=2 max of two.

5. Interviewer follow-ups & drills

Q1. Bug if always both ranges?
Model answer: n=1 both empty or wrong — special case.

Q2. Space opt?
Model answer: Two variables prev/curr per linear.

Q3. Proof?
Model answer: Optimal either skips house0 or house n-1 (cannot take both).

🧩 Pattern · Dynamic Programming

Recognize it: Overlapping subproblems + optimal substructure; “count ways” or “min/max over choices” → memoise or fill a table.

▶ Visualize this problem (step it, predict each fork)
⛶ Open this problem debugger in explore mode
🤖 Don't fully get this? Learn it with Claude

Stuck on House Robber II? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **House Robber II** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **House Robber II** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **House Robber II**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **House Robber II**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Minimum Area RectangleSum of Path Numbers →