House Robber II

Problem

Same as House Robber, except the houses are arranged in a circle — house 0 and house n−1 are now adjacent. Return the maximum amount you can steal without triggering any adjacent pair.

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 1000

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        def line(arr):
            prev = cur = 0
            for x in arr:
                prev, cur = cur, max(cur, prev + x)
            return cur
        return max(line(nums[1:]), line(nums[:-1]))

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
    private int robRange(int[] a, int l, int r) {
        int prev = 0, curr = 0;
        for (int i = l; i <= r; i++) {
            int next = Math.max(curr, prev + a[i]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.