House Robber II

Medium Problem 118 of 151 Java and Python

Practice on LeetCode

Problem

Same as House Robber, but the houses are arranged in a circle: the first house is next to the last one.

Return the maximum amount you can rob without robbing two adjacent houses.

Example 1

Input: nums = [2, 3, 2]
Output: 3
Why: Houses 0 and 2 are adjacent, so rob house 1 only.

Example 2

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

Example 3

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

Constraints

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

Explanation

The circle only adds one rule: you cannot rob both the first and the last house. So at least one of them is skipped.

Solve the straight-line problem twice, once on houses 0 … n - 2 and once on 1 … n - 1, and take the larger result. With a single house, just rob it.

Approach 1 · Naive

Recursion with a "first house taken" flag

Time O(2ⁿ)
Space O(n)

Recurse over the houses, remembering whether house 0 was robbed so the last house can be refused.

best(i, firstTaken) = most money from houses i…n - 1.
At the last house, it may only be robbed if firstTaken is false.
Choose between skipping i and robbing i (then jumping to i + 2).

Java

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(best(nums, 1, false), nums[0] + best(nums, 2, true));
    }

    private int best(int[] nums, int i, boolean firstTaken) {
        int n = nums.length;
        if (i >= n) {
            return 0;
        }
        if (i == n - 1 && firstTaken) {
            return 0;
        }
        return Math.max(best(nums, i + 1, firstTaken), nums[i] + best(nums, i + 2, firstTaken));
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def best(i, first_taken):
            if i >= n or (i == n - 1 and first_taken):
                return 0
            return max(best(i + 1, first_taken), nums[i] + best(i + 2, first_taken))

        return max(best(1, False), nums[0] + best(2, True))

Approach 2 · Optimal

Two linear passes

Time O(n)
Space O(1)

Run the House Robber DP on nums[0..n - 2] and on nums[1..n - 1]; return the larger.

If there is one house, return it.
Return max(line(0, n - 2), line(1, n - 1)), where line is the two-variable House Robber DP over a range.

Java

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 from, int to) {
        int prev2 = 0;
        int prev1 = 0;
        for (int i = from; i <= to; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        def line(houses):
            prev2 = prev1 = 0
            for amount in houses:
                prev2, prev1 = prev1, max(prev1, prev2 + amount)
            return prev1

        if len(nums) == 1:
            return nums[0]
        return max(line(nums[:-1]), line(nums[1:]))

Complexity compared

Approach	Time	Space
Naive Recursion with a "first house taken" flag	O(2ⁿ)	O(n)
Optimal Two linear passes	O(n)	O(1)

Key takeaways

Break a circular constraint by solving the linear problem twice with one end excluded.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem