The O(n) Club: House Robber II: When Your Path Turns Circular (and Paranoid)

The O(n) Club: House Robber II—When Your Path Turns Circular (and Paranoid)

⚡ TL;DR

Old problem: Rob a line of houses, don’t trip two neighbor alarms. New problem: Welcome to the house cul-de-sac—first and last house are instant BFFs. If you rob one, you can’t rob the other. Break the circle (mentally, not physically), run linear DP twice (once skipping house #1, once skipping the caboose), and keep the better stash. Java sketch below:

// Run DP twice: once skipping first house, once skipping last
int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    return Math.max(
        robLinear(nums, 0, nums.length - 2),
        robLinear(nums, 1, nums.length - 1));
}

🧠 How Devs Usually Mess This Up

If you copied your House Robber I code here, check for smoke because something’s overheating. Treating the houses as a line? That’s a surefire route to failure when cases like [2, 999, 2] roll in. Also—big miss—forgetting to split the problem into two runs, and those edge cases? Not everyone remembers that an array of length 1 or 2 can make your code throw a tantrum. Don’t be the dev who flunks the circle, please.

🔍 What’s Actually Going On

Imagine a ring of houses so paranoid, they don’t just care about their next-door neighbors, but the last and first are locking eyes across the cul-de-sac! The trick: consider two scenarios—one where you rob from house 0 to n-2, and one from house 1 to n-1. Each is just House Robber I in disguise! You can even picture them as alternate universes, except instead of Spider-Men you get cash.

Why not both? Because, my friend, if you take both endpoints, the alarm system wins and you sleep in jail. All you have to do is solve both subproblems, then high-five whichever path is richer.

🛠️ PseudoCode

• Edge Cases:
  

  // No houses = 0 loot, one house = instant win
  if (nums.length == 0) return 0;
  if (nums.length == 1) return nums[0];

  If you can’t trip any alarms, just take the money.
• Two Linear DP Robberies:
  

  // Scenario 1: rob 0..n-2, skip last house
  // Scenario 2: rob 1..n-1, skip first house
  maxFromFirst = robLinear(nums, 0, n-2);
  maxFromSecond = robLinear(nums, 1, n-1);
  return Math.max(maxFromFirst, maxFromSecond);
  

  Pretend the neighborhood gate is closed at either end, so you dodge the neighbor constraint.
• Linear DP Helper (House Robber I):

  int robLinear(int[] nums, int start, int end) {
      int prev = 0, curr = 0;
      for (int i = start; i <= end; i++) {
          int temp = Math.max(curr, prev + nums[i]);
          prev = curr;
          curr = temp;
      }
      return curr;
  }

  This is more or less just, “Either rob this place, or sleep outside, your call.”

💻 The Code

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    int maxFromFirst = robLinear(nums, 0, n - 2);
    int maxFromSecond = robLinear(nums, 1, n - 1);
    return Math.max(maxFromFirst, maxFromSecond);
}
 private int robLinear(int[] nums, int start, int end) {
    int prev = 0, curr = 0;
    for (int i = start; i <= end; i++) {
        int temp = Math.max(curr, prev + nums[i]);
        prev = curr;
        curr = temp;
    }
    return curr;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero/one house? Don’t get clever. If there are no houses, you get nothing. One house? Walk right in.
• Two houses? Pick the fatter wallet. Don’t try to be a hero and rob both; alarms go off.
• Forgetting to split into two linear runs: That’s the Big Circular Sin.
• Off-by-one errors: You don’t want to miss the last house or sneak back into the first.
• Time/Space O(n)/O(1): No heavy-lifting—just two passes, no bag full of arrays.

🧠 Interviewer Brain-Tattoo

“If your algorithm goes in circles, split the loop and rob twice—otherwise, the circle robs you.”