House Robber II

---

House Robber II: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and
then rob house 3 (money = 2), because they are adjacent houses.

---

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

---

Example 3:

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

---

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

---

Try this Problem on your own or check similar problems:

1. Maximum Product Subarray
2. House Robber
3. House Robber III

Solution:

Java

public int rob(int[] nums) {
    if(nums.length == 1) return nums[0];

    int twoStepsBefore = 0, oneStepBefore = 0;
    for(int i = 0; i < nums.length - 1; ++i){
        int current = Math.max(nums[i] + twoStepsBefore, oneStepBefore);
        twoStepsBefore = oneStepBefore;
        oneStepBefore = current;
    }

    int max = oneStepBefore;

    twoStepsBefore = 0;
    oneStepBefore = 0;
    for(int i = 1; i < nums.length; ++i){
        int current = Math.max(nums[i] + twoStepsBefore, oneStepBefore);
        twoStepsBefore = oneStepBefore;
        oneStepBefore = current;
    }


    return Math.max(max, oneStepBefore);
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  if (nums.length === 1) return nums[0];

  let twoStepsBefore = 0,
    oneStepBefore = 0;
  for (let i = 0; i < nums.length - 1; ++i) {
    let current = Math.max(nums[i] + twoStepsBefore, oneStepBefore);
    twoStepsBefore = oneStepBefore;
    oneStepBefore = current;
  }

  let max = oneStepBefore;

  twoStepsBefore = 0;
  oneStepBefore = 0;
  for (let i = 1; i < nums.length; ++i) {
    let current = Math.max(nums[i] + twoStepsBefore, oneStepBefore);
    twoStepsBefore = oneStepBefore;
    oneStepBefore = current;
  }

  return Math.max(max, oneStepBefore);
};

Python

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

        twoStepsBefore = 0
        oneStepBefore = 0
        for i in range(len(nums) - 1):
            current = max(nums[i] + twoStepsBefore, oneStepBefore)
            twoStepsBefore = oneStepBefore
            oneStepBefore = current

        maximum = oneStepBefore

        twoStepsBefore = 0
        oneStepBefore = 0
        for i in range(1, len(nums)):
            current = max(nums[i] + twoStepsBefore, oneStepBefore)
            twoStepsBefore = oneStepBefore
            oneStepBefore = current

        return max(maximum, oneStepBefore)

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];

        int twoStepsBefore = 0, oneStepBefore = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            int current = max(nums[i] + twoStepsBefore, oneStepBefore);
            twoStepsBefore = oneStepBefore;
            oneStepBefore = current;
        }

        int maximum = oneStepBefore;

        twoStepsBefore = 0;
        oneStepBefore = 0;
        for (int i = 1; i < nums.size(); ++i) {
            int current = max(nums[i] + twoStepsBefore, oneStepBefore);
            twoStepsBefore = oneStepBefore;
            oneStepBefore = current;
        }

        return max(maximum, oneStepBefore);
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

Almost the same problem as House Robber so we reuse the solution and break the problem into two subproblems (because of the circle nature of the problem):

• we skip the last house and have the first one as candidate
• we skip the first house and have the last one as candidate

We solve the subproblem same we did in House Robber and return the larger result value of those two subproblems. Notice that we're saying that we're picking the last or first as candidate, we're not immediately choosing it since they can be skipped based on the loop logic. Let's say we're in the first loop, we picked first as candidate and skipped the last, but let's say nums[1] > nums[0] + nums[2], that means we're picking the second element instead of the sum of the first and third, so we skipping the first element. Now you can ask yourself well if omitted the first, can't we include the last? You are right, this sequence will be picked in the second loop when we can pick the last and (already) skipped first element.

Since in the first loop we're skipping the last, and in the second loop skipping the first, what happens if we have only one element in input array? Well, it's both the first and the last element, so we will skip in both loops. To solve this we just check if we only have one element and return it's value if(nums.length == 1) return nums[0]; since that's the maximum robber can rob.