House Robber

198.House Robber

Array

Dynamic Programming

Problem Statement:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. If two adjacent houses are robbed, the police will be notified. Given an array of non-negative integers representing the amount of money at each house, determine the maximum amount you can rob without alerting the police.

Example:

Input:

nums = [1,2,3,1]

→

Output:

4

Algorithm:

1. Track max money from two houses back
2. Track max money from previous house
3. Current max is max of (current + twoBefore) or oneBefore
4. Update previous values for next iteration

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    
    int twoBefore = nums[0];  // Max money if we rob two houses back
    int oneBefore = Math.max(nums[0], nums[1]);  // Max money from previous house
    int max = 0;
    
    for (int i = 2; i < nums.length; i++) {
        int currHouse = nums[i];
        max = Math.max(currHouse + twoBefore, oneBefore);  // Choose better option
        twoBefore = oneBefore;
        oneBefore = max;
    }
    
    return max;
}

Python Solution:

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
        
    two_before = nums[0]
    one_before = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        curr_max = max(nums[i] + two_before, one_before)
        two_before = one_before
        one_before = curr_max
        
    return one_before

C++ Solution:

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        
        int two_before = nums[0];
        int one_before = max(nums[0], nums[1]);
        int curr_max = one_before;
        
        for(int i = 2; i < nums.size(); i++) {
            curr_max = max(nums[i] + two_before, one_before);
            two_before = one_before;
            one_before = curr_max;
        }
        
        return curr_max;
    }
};