leetcode-textbook

0213 - House Robber II

Difficulty: Medium Pattern: 1-D DP LeetCode: https://leetcode.com/problems/house-robber-ii/

Problem

Same as House Robber, but the houses are arranged in a circle: the first and last houses are also adjacent. So you cannot rob both house 0 and house n-1. Return the maximum money you can rob without triggering the alarm.

Signature:

int rob(int[] nums)

Examples (verbatim from LeetCode):

Input:  nums = [2,3,2]
Output: 3
Explanation: house 0 and house 2 are adjacent in the circle, so rob only house 1.

Input:  nums = [1,2,3,1]
Output: 4
Explanation: rob house 0 (1) and house 2 (3) = 4. House 3 is NOT robbed.

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

Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 1000.

Intuition

The circular adjacency is the only new wrinkle; the inner problem is still House Robber I. The trick is to split into the two linear cases that the circle forbids simultaneously:

Every legal robbery falls into at least one of these two cases (you rob the first, or you don’t — and if you do, you can’t rob the last). So the answer is max(rob_linear(0..n-2), rob_linear(1..n-1)). The single-house case must be handled separately because both slices would be empty.

This is a recurring DP meta-pattern: when a constraint makes the state hard to define, split the input so the constraint disappears in each piece, then take the best over the pieces.

Checkpoint A – Break the circle

Pause and answer before expanding. Wrong guesses teach more than fast right ones.

Q1 (recall). House Robber II solves the circle by running House Robber I on how many linear slices, then taking the max?

Show answer **(b)** -- exclude the last house, or exclude the first house. Every legal plan appears in at least one slice, since you either rob the first house or you don't.

Q2 (comprehend). Why must a single-house array be handled before slicing?

Show answer **(b)** -- robLinear(0, n-2) would become robLinear(0,-1), an empty range; the n==1 guard returns nums[0] directly before any slice is taken.

Pseudocode

function rob(nums):
    n = length of nums
    if n is 1: return nums[0]
    if n is 2: return max(nums[0], nums[1])

    # Case A: exclude the last house -> rob linear over [0..n-2]
    bestA = robLinear(nums, 0, n - 2)
    # Case B: exclude the first house -> rob linear over [1..n-1]
    bestB = robLinear(nums, 1, n - 1)
    return max(bestA, bestB)


# Standard House Robber I on the inclusive slice [lo..hi].
function robLinear(nums, lo, hi):
    prev2 = 0                       # best of empty prefix
    prev1 = nums[lo]                # best of first house
    for i from lo+1 to hi:
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current
    return prev1

robLinear is exactly the House Robber I recurrence; the only change is that we walk an explicit [lo..hi] slice instead of the whole array.

Java Solution

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // Either skip the last house (range [0..n-2]) or skip the first ([1..n-1]).
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

    private int robLinear(int[] nums, int lo, int hi) {
        int prev2 = 0;
        int prev1 = nums[lo];
        for (int i = lo + 1; i <= hi; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

The n == 1 guard is essential: with one house the two slices would be empty and robLinear(nums, 0, -1) would read nums[0] from an empty range. robLinear is the House Robber I algorithm verbatim, restricted to [lo..hi]. We pay for the helper with a second pass, doubling the time constant, but the asymptotic complexity is still O(n). No extra space is used.

Complexity

Time:  O(n)   -- two linear scans (one for each slice); each is O(n).
Space: O(1)   -- the helper uses two rolling variables.

Dry-Run

Step-by-step on nums = [2, 3, 2]:

Case A: slice [0..1] = [2, 3] (skip last house)

i prev2 prev1 skip: prev1 rob: prev2 + nums[i] current
- 0 2 - - init
1 0 2 2 0 + 3 = 3 3

bestA = 3.

Case B: slice [1..2] = [3, 2] (skip first house)

i prev2 prev1 skip: prev1 rob: prev2 + nums[i] current
- 0 3 - - init
2 0 3 3 0 + 2 = 2 3

bestB = 3.

Answer: max(3, 3) = 3. Rob only house 1.

Notice the two slices overlap on the middle house but never include both ends at once, which is exactly the constraint the circle imposes.

Checkpoint B – Trace both slices

Q1 (apply). Trace nums = [2, 7, 9, 3]. What does rob return?

Show answer **(b)** -- Case A on [2,7,9] gives 11 (rob 2 and 9); Case B on [7,9,3] gives 10 (rob 7 and 3); max(11,10)=11.

Q2 (analyze). On nums = [2, 3, 2], what would happen if you ran House Robber I on the WHOLE array instead of slicing?

Show answer **(b)** -- ignoring the circle treats houses 0 and 2 as non-adjacent, so it returns 4 by robbing both; the circle makes them adjacent, so the true answer is 3.

Q3 (transfer). If the houses formed TWO separate circles instead of one, how would you extend the approach in one sentence?

Show answer Run the two-slice trick independently on each circle, then sum the results -- each circle is a self-contained House Robber II, and the circles do not interact.

Common mistakes