Start practising

House Robber II

Medium Dynamic Programming Alternate Selection / Pick / Not pick Original on LeetCode

House Robber II is a medium dynamic programming problem solved with the alternate selection / pick / not pick pattern. The best approach, optimal (linear house robber, twice), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from recursion on two ranges up.

Problem

Same as House Robber, but the houses are arranged in a circle, so the first and last houses are neighbours. Return the maximum amount you can rob without robbing two adjacent houses.

Examples

Example 1

Input
nums = [2, 3, 2]
Output
3
Why
Houses 0 and 2 are neighbours in a circle.

Example 2

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

Constraints

  • 1 <= nums.length <= 100.
  • The houses form a circle: the first and last are adjacent.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Recursion on two rangesO(2ⁿ)O(n)
Optimal (linear House Robber, twice)O(n)O(1)

1Recursion on two ranges

TimeO(2ⁿ)
SpaceO(n)

Run the pick / not-pick recursion on nums[0..n-2] and on nums[1..n-1], and take the better result.

  1. If n == 1 return nums[0].
  2. max(best(0, n - 2), best(1, n - 1)).
Java
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(best(nums, 0, n - 2), best(nums, 1, n - 1));
    }

    private int best(int[] a, int lo, int i) {
        if (i < lo) return 0;
        return Math.max(best(a, lo, i - 1), a[i] + best(a, lo, i - 2));
    }
}

2Optimal (linear House Robber, twice)

TimeO(n)
SpaceO(1)

Break the circle by excluding one end at a time, and run the O(1)-space House Robber on each range.

  1. If n == 1 return nums[0].
  2. Return max(line(0, n - 2), line(1, n - 1)).
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[] a, int lo, int hi) {
        int prev2 = 0, prev1 = 0;
        for (int i = lo; i <= hi; i++) {
            int cur = Math.max(prev1, prev2 + a[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Edge cases to test

  • Single house (the two ranges would both be empty)
  • Two houses

Hints

Hint 1

You cannot rob both the first and the last house. So solve House Robber twice: without the last house, and without the first.

FAQ

What is the best time complexity for House Robber II?

Optimal (linear House Robber, twice) runs in O(n) time and O(1) extra space.

Which pattern does House Robber II use?

It is a dynamic programming problem that uses the alternate selection / pick / not pick pattern. Other problems with the same pattern: House Robber.

Is there a brute force solution for House Robber II?

Yes. Recursion on two ranges takes O(2ⁿ) time and O(n) space. Run the pick / not-pick recursion on nums[0..n-2] and on nums[1..n-1], and take the better result.

Which edge cases should I test for House Robber II?

Single house (the two ranges would both be empty); Two houses.