House Robber

---

House Robber: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 = [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 2:

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

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

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

Solution:

Java

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

    return oneStepBefore;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  let twoStepsBefore = 0;
  let oneStepBefore = 0;

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

  return oneStepBefore;
};

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        twoStepsBefore = 0
        oneStepBefore = 0

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

        return oneStepBefore

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int twoStepsBefore = 0;
        int oneStepBefore = 0;

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

        return oneStepBefore;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

For each element in array, we have to make a decision if we're going to choose it and add it up to the sum not including the element just before the current element, or are we going to skip it and propagate the sum accumulated using the element before. We can make the decision based on what sum is larger, to keep the subresults, we store them in helper array dp:

Java

public int rob(int[] nums) {
    int[] dp = new int[nums.length + 1];
    dp[1] = nums[0];
    for(int i = 2; i <= nums.length; ++i){
        dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
    }

    return dp[nums.length];
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const dp = new Array(nums.length + 1).fill(0);
  dp[1] = nums[0];

  for (let i = 2; i <= nums.length; ++i) {
    dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
  }

  return dp[nums.length];
};

Python

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

      for i in range(2, len(nums) + 1):
          dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])

      return dp[len(nums)]

C++

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

      for (int i = 2; i <= nums.size(); ++i) {
          dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
      }

      return dp[nums.size()];
    }
};

But notice that it can be optimized further since we're only using element just before the current element, and the element that comes two steps before (index-2). So, we only need two variables to track the state twoStepsBefore and oneStepBefore. And at each element we calculate if it's better for us to choose nums[i] + twoStepsBefore (pick the current element) or oneStepBefore (omit the current element). The final solution is given in the Solution section.