Command Palette

Search for a command to run...

Hectal
Problem 28.4 · DP Foundations: 1DMedium

House Robber II

Pattern1D Dynamic Programming

What it teaches: Break a circle into two lines: exclude the first house or exclude the last.

Practise it on judges as “House Robber II”.

The problem

The houses form a circle, so the first and last are neighbours. Return the most money you can rob without robbing adjacent houses.

Example 1

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

Constraints

  • 1 ≤ n ≤ 100

Pattern clues in the wording

  • → Circular adjacency

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int rob(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [2,3,2]
3
2
nums = [1,2,3,1]
4
3
nums = [1,2,3]
3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Two linear passes · O(n)
1

Two linear passes

Time O(n) Space O(1)

max(rob(0..n−2), rob(1..n−1)), with a special case for one house.

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

Verdict: Reuses House Robber.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One house
  • Two houses

Mistakes people make

  • Running the linear version once on the whole circle.

Interview

Follow-up questions

Why do two cases cover everything?