#213 House Robber II
the problem
In plain words
Same as House Robber, but the houses stand in a circle: the first and last houses are neighbours.
in nums = [2,3,2]
out 3
Houses 0 and 2 are neighbours, so rob house 1.
in nums = [1,2,3,1]
out 4
in nums = [1,2,3]
out 3
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
You can't rob both the first and the last house. So the answer is the better of two straight streets: houses 0..n−2 and houses 1..n−1.
solutions
From brute force to optimal
Run the take/skip recursion on each straight street.
- n = 1 → nums[0].
- Return max(best(0..n−2), best(1..n−1)).
Exponential take/skip tree, twice.
Recursion depth.
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; // first and last are neighbours: never rob both, so solve two straight lines return Math.max(best(nums, 0, n - 2), best(nums, 1, n - 1)); } /** Best loot from houses i..end (a straight street). */ private int best(int[] nums, int i, int end) { if (i > end) return 0; return Math.max(nums[i] + best(nums, i + 2, end), best(nums, i + 1, end)); }}Cache best(i) — a fresh memo for each street.
- Two memoized runs, take the max.
≤ n states per run, two runs.
Memo + stack.
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; return Math.max(line(nums, 0, n - 2), line(nums, 1, n - 1)); } private int line(int[] nums, int start, int end) { int[] memo = new int[nums.length]; // fresh memo per street Arrays.fill(memo, -1); return best(nums, start, end, memo); } private int best(int[] nums, int i, int end, int[] memo) { if (i > end) return 0; if (memo[i] != -1) return memo[i]; return memo[i] = Math.max(nums[i] + best(nums, i + 2, end, memo), best(nums, i + 1, end, memo)); }}House Robber I with rolling variables on each range.
- robLine(0, n−2) and robLine(1, n−1).
- Return the max (special-case n = 1).
Two linear passes.
Two variables per pass.
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; // first and last are neighbours: drop the last house, then drop the first return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1)); } /** House Robber I on nums[lo..hi] with O(1) space. */ private int robLine(int[] nums, int lo, int hi) { int prev2 = 0, prev1 = 0; for (int i = lo; i <= hi; i++) { int cur = Math.max(prev1, prev2 + nums[i]); // skip it, or rob it prev2 = prev1; prev1 = cur; } return prev1; }}Break the circle into two streets
in the room
How to say it in the interview
talk track
- Say "break the circle": first and last can't both be robbed, so solve two lines and reuse House Robber I.
- Handle n = 1 before anything else — both ranges would be empty.
traps
- n = 1: both ranges are empty — return nums[0] directly.
- Sharing one memo between the two streets gives wrong cached values.
what they ask next
Follow-ups
Houses on a binary tree (LC 337)?
Each node returns two numbers — best if it's robbed, best if it isn't — and its parent combines them. That's DP on trees.
before you submit
Edge cases to test
- One house → nums[0] (both streets would be empty).
- Two houses → the richer one: they are neighbours.
- [1000,1,1,1000] → 1001: the two rich ends touch.
practise next
Similar problems
- #198House RobberMediumin Dynamic Programming
- #70Climbing StairsEasyin Dynamic Programming