Difficulty: Medium1-D Dynamic Programming

House Robber II

Problem in Plain English

Given cash in houses arranged in a circle, rob the largest total possible where both adjacent houses and the first-last pair cannot be robbed together.

Problem Statement

You are given an integer array nums where nums[i] is the money in house i, and the houses form a circle: house 0 and house n - 1 are adjacent. Robbing two adjacent houses triggers the alarm.

Return the maximum money robbable with no two robbed houses adjacent around the circle. With a single house, its value is the answer.

Constraints

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

Examples

Example 1

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

Houses 1 and 3 are adjacent around the circle, so rob house 2 alone for 3.

Example 2

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

Rob house 1 (money 1) and house 3 (money 3) for a total of 4.

Example 3

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

Robbing house 3 alone for 3 beats every pair, since houses 1 and 3 are now neighbours.

Example 4

Input: nums = [7]
Output: 7

A single house is not a conflicting pair with itself. Rob it for 7; removing either endpoint would incorrectly leave an empty line.

Intuition

The circle adds one conflict: the first and last houses are neighbours. In Example 1, [2, 3, 2], taking both endpoint values would give 4 but trigger the alarm. Every valid plan leaves at least one endpoint unrobbed. Solve the line without the last house and the line without the first, then keep the richer answer. Within either line, each house is a choice between skipping it and taking it with the best plan that ends two houses earlier.

Approaches

Recursive Take Or Skip

Solution Details

Reveal Recursive Take Or Skip: intuition, complexity, and code

Intuition

Partition plans by whether house 0 is robbed. Taking it banks its value and removes both neighbours, leaving indices 2 through n - 2; skipping it leaves indices 1 through n - 1. In either remaining line, recursively try skipping each house or taking it and jumping over its neighbour. Repeated calls for the same tail explain the exponential cost.

Step-by-Step Logic

Handle a single house directly. Otherwise split by taking or skipping index 0; in Example 1, [2, 3, 2], the take case starts with 2.
When taking index 0, recurse only over indices 2 through n - 2, excluding both neighbours. In Example 1 that range is empty, so the case total is 2 + 0 = 2.
When skipping index 0, recurse over indices 1 through n - 1. At every available index compare skipping it with taking its value and advancing two positions. For Example 1 the line [3, 2] has best total 3.
Return the larger case total. Example 1 returns max(2, 3) = 3.

Why It Works

For a fixed line ending at end, let dfs(i, end) mean the maximum loot available from index i onward. Past end, no houses remain and the answer is 0. Every valid plan either skips i, giving dfs(i + 1, end), or takes i and must skip its neighbour, giving nums[i] + dfs(i + 2, end). These branches exhaust all valid choices, and each combines only nonadjacent houses. By induction on the remaining line length, taking their maximum is optimal. For the circle, every plan either takes house 0 or skips it. The take case excludes indices 1 and n - 1, while the skip case removes the wraparound conflict entirely. These two cases cover every valid circular plan, so their maximum is the required answer; the single-house guard handles the case where there is no distinct neighbour.

Dry Run

Recursive Take Or Skip: variable states at each step
call ID (assigned on entry)	case	call returning (return order)	branch totals	returned best
1	take first	dfs(2, 1)	empty range	0
case A	take first	bank 2	2 + 0	2
4	skip first	dfs(3, 2)	empty range	0
5	skip first	dfs(4, 2)	empty range	0
3	skip first	dfs(2, 2)	skip 0; take 2 + 0 = 2	2
6	skip first	dfs(3, 2)	empty range	0
2	skip first	dfs(1, 2)	skip 2; take 3 + 0 = 3	3
answer	compare cases	max(2, 3)	return	3

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the number of houses. The call count satisfies a Fibonacci-like recurrence because the branches advance by one and two, so O(2^n) is a valid loose exponential upper bound, not an exact doubling per house. Splitting into two circular cases changes only a constant factor. At most O(n) frames are simultaneously live. Each frame stores a few scalars; no slices, result arrays or memo tables are allocated, and the input is unchanged. This uncached approach is for teaching and is impractical near n = 100.

Code

Solution.java

1class Solution {2    public int rob(int[] nums) {3        int n = nums.length;4        if (n == 1) {5            return nums[0];6        }7        // Taking index 0 excludes both neighbours: 1 and n - 1.8        int robFirst = nums[0] + dfs(nums, 2, n - 2);9        int skipFirst = dfs(nums, 1, n - 1);10        return Math.max(robFirst, skipFirst);11    }12
13    private int dfs(int[] nums, int i, int end) {14        if (i > end) {15            return 0;16        }17        int skip = dfs(nums, i + 1, end);18        // Taking this house skips its adjacent successor.19        int take = nums[i] + dfs(nums, i + 2, end);20        return Math.max(skip, take);21    }22}

Hints

Hint 1

The circle has exactly one extra rule beyond the street version: houses 0 and n - 1 are neighbours.

Hint 2

That rule forbids a single pair, so decide the fate of house 0 first and solve the remaining line both ways.

Hint 3

Run the linear robber on 0..n-2 and on 1..n-1, then keep the richer run.

Edge Cases

One house has no neighbour conflict, so its value is the answer and both ranges would be empty.
Two houses return the richer one, since each run covers exactly one house.
All zeros return 0 from either run without special handling.

Common Mistakes and Interview Tips

Running the linear solver on the full circle double-counts the forbidden pair on inputs like [2, 3, 2].
Forgetting the single-house guard makes both ranges empty and returns 0 instead of the house value.
Solving the same shortened line twice misses plans that require the excluded endpoint. For [1, 2, 3, 9], dropping the last house twice gives only 4 instead of the correct 11 from indices 1 and 3.
Do not add the two range answers: they are competing complete plans and may share houses. In an interview, justify both coverage of every circular plan and validity of each shortened line.

Key Takeaway

Break a circular adjacency ban by branching on one member of the wrapped pair; each branch is a line problem solvable with the same rolling recurrence.