Crack the Backend

Problem Statement

You are a robber planning to rob houses along a street. Each house i has a non-negative amount of money nums[i]. You cannot rob two adjacent houses (if you rob house i, you cannot rob house i-1 or i+1). Return the maximum amount of money you can rob tonight.

The array nums gives the money at each house; you can choose which houses to rob subject to the no-adjacent constraint.
Empty array: return 0. Single house: return that house's value.

Key Observations

At each house i, we have two choices: rob it (then we cannot have robbed i-1, so we take nums[i] + best from [0..i-2]) or skip it (then we take best from [0..i-1]). So dp[i] = max(dp[i-1], nums[i] + dp[i-2]).
dp[i] represents the maximum money we can get from the first i+1 houses (indices 0..i) subject to the constraint. Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
We only need the last two values, so space can be O(1).

Approach

High-level: dp[i] = maximum money from houses [0..i] with no two adjacent robbed. Transition: either skip house i (dp[i-1]) or rob house i (nums[i] + dp[i-2]). Take the maximum.

Steps:

If nums is empty, return 0. If length 1, return nums[0]. Set prev2 = nums[0], prev1 = max(nums[0], nums[1]).
For i from 2 to n-1: cur = max(prev1, nums[i] + prev2); then prev2 = prev1, prev1 = cur.
Return prev1.

Implementation

Java

public int rob(int[] nums) {
    int n = nums.length;

    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return nums[0];
    }

    int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < n; i++) {
        int cur = Math.max(prev1, nums[i] + prev2);
        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

Test Cases

Example 1

Input

nums = [1,2,3,1]

Expected

4

Explanation

Rob house 0 and 2.

Complexity Analysis

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

Follow-ups

House Robber II: houses are arranged in a circle (first and last adjacent).