House Robber II

House Robber II adds one small twist to a classic dynamic programming problem. Dynamic programming is a way to solve a big problem by breaking it into small pieces, solving each piece once, and saving the answer. The twist here is that the houses form a circle. That circle changes everything. So the interviewer wants to see if you can turn a hard circular problem into two easy straight-line problems.

🎯 The Problem

You are robbing houses that hold money. Take the most money you can without setting off an alarm.

The rules:

• If you rob two houses that sit next to each other, the alarm rings. So you can never pick two neighbors.
• The houses are arranged in a circle. So the first house and the last house are neighbors too.
• That means you cannot rob both ends.
• Return the most money you can take.

For the money [2, 3, 2], house 0 and house 2 are neighbors in the circle. You cannot take both 2s. The best single choice is the middle house, which is 3.

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

Explanation: Houses 0 and 2 are neighbors in the circle, so you cannot rob both.
The best is to rob house 1 alone for 3.

This diagram shows why the circle is the hard part. The dashed line is the extra neighbor rule that the circle adds.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: at each house, rob or skip, and run the whole thing twice to break the circle.

The idea:

• At each house you either rob it or skip it.
• If you rob it, you must skip the next one.
• If you skip it, you move to the next.

How it works:

• A function from a house returns the most money from there onward.
• One branch robs the house and jumps two ahead. The other skips it and moves one ahead. Take the bigger.
• To handle the circle, run this twice: once allow the first house but ban the last, once ban the first but allow the last. Take the bigger run.

Why it is weak:

• The same house gets asked the same question again and again.
• These repeats are called overlapping subproblems.
• The work doubles at each house, so it is about O(2ⁿ). Too slow.

Here is the plain recursion code:

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    def line(start, end):
        def dfs(i):
            if i > end:
                return 0
            return max(nums[i] + dfs(i + 2), dfs(i + 1))
        return dfs(start)

    return max(line(0, len(nums) - 2), line(1, len(nums) - 1))

🧠 Approach 2: Memoization (Better)

The idea in one line: store each house’s answer so you never recompute it.

The idea:

• Keep an array called memo.
• The first time you solve a house, store its answer.

How it works:

• Run the same two-pass recursion.
• Before computing a house, check the cache.
• The next time the house appears, read it.

Why it is fast:

• Each house is solved once per run, and each run is O(n).
• So the whole thing is O(n). This is memoization.

Here is the memoized recursion:

from functools import lru_cache


def rob(nums):
    if len(nums) == 1:
        return nums[0]

    def line(start, end):
        @lru_cache(None)
        def dfs(i):
            if i > end:
                return 0
            return max(nums[i] + dfs(i + 2), dfs(i + 1))
        return dfs(start)

    return max(line(0, len(nums) - 2), line(1, len(nums) - 1))

📊 Approach 3: Bottom-Up Tabulation (Better)

The idea in one line: fill a table for a straight line, then call it twice for the circle.

The idea:

• Make a helper that solves a plain straight line of houses with an array dp.
• dp[i] is the most money from the first house up to house i.

How it works:

• At each house dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Skip this house, or rob it plus the best two back.
• Call the helper on houses 0 to n-2. Then on houses 1 to n-1.
• The answer is the bigger of the two.

Why it is fine:

• Each cell is filled once, so each run is O(n).
• No recursion stack. This is tabulation.

This diagram shows the table filling for the straight line [2, 3, 2]. Each cell picks the better of skip or rob.

⚡ Approach 4: Space-Optimized (Best)

The idea in one line: the table only needs the last two values, so keep two numbers.

The idea:

• The table only ever uses the two cells before the current one.
• So drop the full array and keep two numbers that slide forward.

How it works:

• Write a helper rob_line that solves a straight slice with two running values.
• Run it twice: one run skips the last house, one run skips the first house.
• Return the bigger result. If there is only one house, just return it, since there is no neighbor.

Why it is best:

• It keeps O(n) time.
• The memory drops to O(1) since only two values are alive.

Steps to Solve

1. If there is only one house, return its money. The circle rule does not apply.
2. Write a helper that robs a straight line using two running values, prev2 and prev1.
3. In the helper, for each house compute current = max(prev1, prev2 + money), then slide forward.
4. Run the helper on houses 0 to n-2, which skips the last house.
5. Run the helper on houses 1 to n-1, which skips the first house.
6. Return the bigger of the two runs.

#include <stdio.h>

int maxVal(int a, int b) {
    return a > b ? a : b;
}

// most money from nums[start..end] in a straight line
int robLine(int nums[], int start, int end) {
    int prev2 = 0;  // best up to two houses back
    int prev1 = 0;  // best up to one house back
    for (int i = start; i <= end; i++) {
        int current = maxVal(prev1, prev2 + nums[i]);
        prev2 = prev1;   // slide forward
        prev1 = current;
    }
    return prev1;
}

int rob(int nums[], int n) {
    if (n == 1) {
        return nums[0];  // only one house, no neighbor
    }
    int skipLast = robLine(nums, 0, n - 2);   // ban the last house
    int skipFirst = robLine(nums, 1, n - 1);  // ban the first house
    return maxVal(skipLast, skipFirst);
}

int main(void) {
    int nums[] = {2, 3, 2};
    int n = 3;
    printf("%d\n", rob(nums, n));
    return 0;
}

3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// most money from nums[start..end] in a straight line
int robLine(vector<int>& nums, int start, int end) {
    int prev2 = 0;  // best up to two houses back
    int prev1 = 0;  // best up to one house back
    for (int i = start; i <= end; i++) {
        int current = max(prev1, prev2 + nums[i]);
        prev2 = prev1;   // slide forward
        prev1 = current;
    }
    return prev1;
}

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) {
        return nums[0];  // only one house, no neighbor
    }
    int skipLast = robLine(nums, 0, n - 2);
    int skipFirst = robLine(nums, 1, n - 1);
    return max(skipLast, skipFirst);
}

int main() {
    vector<int> nums = {2, 3, 2};
    cout << rob(nums) << endl;
    return 0;
}

3

public class HouseRobberII {
    // most money from nums[start..end] in a straight line
    static int robLine(int[] nums, int start, int end) {
        int prev2 = 0;  // best up to two houses back
        int prev1 = 0;  // best up to one house back
        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;   // slide forward
            prev1 = current;
        }
        return prev1;
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];  // only one house, no neighbor
        }
        int skipLast = robLine(nums, 0, n - 2);
        int skipFirst = robLine(nums, 1, n - 1);
        return Math.max(skipLast, skipFirst);
    }

    public static void main(String[] args) {
        int[] nums = { 2, 3, 2 };
        System.out.println(rob(nums));
    }
}

3

def rob_line(nums, start, end):
    # most money from nums[start..end] in a straight line
    prev2 = 0   # best up to two houses back
    prev1 = 0   # best up to one house back
    for i in range(start, end + 1):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1            # slide forward
        prev1 = current
    return prev1


def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]           # only one house, no neighbor
    skip_last = rob_line(nums, 0, n - 2)   # ban the last house
    skip_first = rob_line(nums, 1, n - 1)  # ban the first house
    return max(skip_last, skip_first)


nums = [2, 3, 2]
print(rob(nums))

3

function robLine(nums, start, end) {
  // most money from nums[start..end] in a straight line
  let prev2 = 0; // best up to two houses back
  let prev1 = 0; // best up to one house back
  for (let i = start; i <= end; i++) {
    const current = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1; // slide forward
    prev1 = current;
  }
  return prev1;
}

function rob(nums) {
  const n = nums.length;
  if (n === 1) {
    return nums[0]; // only one house, no neighbor
  }
  const skipLast = robLine(nums, 0, n - 2);
  const skipFirst = robLine(nums, 1, n - 1);
  return Math.max(skipLast, skipFirst);
}

const nums = [2, 3, 2];
console.log(rob(nums));

3

Let us walk through the Python version line by line and see why each piece is there.

def rob_line(nums, start, end):
    prev2 = 0
    prev1 = 0
    for i in range(start, end + 1):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current
    return prev1

The helper rob_line solves a plain straight line of houses. The two lines prev2 = 0 and prev1 = 0 start both running values at zero. Here prev1 is the best money up to the house just before. And prev2 is the best up to two houses before. We start at zero because before the first house we have robbed nothing.

The loop walks each house in the slice. The line current = max(prev1, prev2 + nums[i]) is the key choice. You either skip this house, which keeps prev1. Or you rob this house, which means you add its money to prev2, the best from two houses back. You take the bigger of the two. Then prev2 = prev1 and prev1 = current slide the window one house forward.

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    skip_last = rob_line(nums, 0, n - 2)
    skip_first = rob_line(nums, 1, n - 1)
    return max(skip_last, skip_first)

The line if n == 1 handles the lone house. With one house there is no neighbor, so the circle rule does nothing. We just take that house. The two calls to rob_line break the circle. The first run uses houses 0 to n-2, so it never robs the last house. The second run uses houses 1 to n-1, so it never robs the first house. Since the first and last are the only forbidden pair, banning one of them in each run is enough. The final max picks the better of the two runs.

⏱️ Time and Space Complexity

Plain recursion repeats work, so it blows up to O(2ⁿ). Memoization and tabulation solve each house once, twice over, so they stay O(n). The space-optimized version also runs in O(n) time but keeps only a couple of numbers, so its memory is O(1).

🧩 Key Takeaways

• ✅ The houses form a circle, so the first and last house count as neighbors.
• ✅ Break the circle into two straight lines. Skip the first house once, skip the last house once.
• ✅ For a straight line, at each house choose the better of skipping it or robbing it plus the best two back.
• ✅ Plain recursion repeats overlapping subproblems, so it is O(2ⁿ). Saving answers makes it O(n).
• ✅ Each step needs only the last two values, so two variables replace the whole array for O(1) space.

🚀 What’s Next?

• Min Cost Climbing Stairs
• Decode Ways