House Robber: cannot rob adjacent houses

• House Robber – a one-dimensional decision DP where each element has a binary choice: take or skip.
• Recurrence – dp[i] = max(dp[i-1], nums[i] + dp[i-2]), encoding that robbing house i forbids house i-1.
• Rolling variables – since dp[i] depends only on the two preceding values, two variables replace the full array.
• Time – O(n) with a single pass through the array.
• Space – O(1) when using two rolling variables instead of an array.

What is the House Robber problem?

The House Robber problem gives you an array of non-negative integers where each element represents the value stored in a house along a street. You want to maximize the total value you collect, but you cannot collect from two adjacent houses. If you take house i, you must skip house i-1 and house i+1.

In banking terms, the National Bank of India picks non-adjacent promotional time slots to maximize total campaign revenue without fatiguing customers with back-to-back promotions.

Why does a DP approach work here?

At each house you face a binary decision: rob it or skip it. If you rob it, you earn its value plus the best you could achieve up to two houses back (since the adjacent house is forbidden). If you skip it, you carry forward the best you could achieve up to the previous house. This gives overlapping subproblems with optimal substructure, the two hallmarks of dynamic programming.

A greedy approach fails because taking the locally largest house can block access to a pair of houses that together yield more.

// Greedy fails: houses = [2, 7, 9, 3, 1]
// Greedy picks 9 (largest), skips 7 and 3, then picks 2 and 1 = 12
// Optimal: 2 + 9 + 1 = 12 (same here, but consider [2, 1, 1, 2])
// Greedy picks 2 (first or last), misses 2+2=4

How does the recurrence work?

The recurrence is dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]). The first term is the skip case: the best total through house i-1 carries forward. The second term is the rob case: the value of house i plus the best total through house i-2, because robbing i forbids i-1.

Base cases: dp[0] = nums[0] (only one house, rob it) and dp[1] = Math.max(nums[0], nums[1]) (two houses, pick the better one).

package com.bank.service;

public class PromotionSlotSelector {

    public static int maxRevenue(int[] slotValues) {
        if (slotValues == null || slotValues.length == 0) return 0;
        if (slotValues.length == 1) return slotValues[0];

        int[] dp = new int[slotValues.length];
        dp[0] = slotValues[0];
        dp[1] = Math.max(slotValues[0], slotValues[1]);

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

How do you optimise space with rolling variables?

Since dp[i] depends only on dp[i-1] and dp[i-2], you replace the entire array with two variables. This reduces space from O(n) to O(1).

package com.bank.service;

public class PromotionSlotSelectorOptimised {

    public static int maxRevenue(int[] slotValues) {
        if (slotValues == null || slotValues.length == 0) return 0;
        if (slotValues.length == 1) return slotValues[0];

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

        for (int i = 2; i < slotValues.length; i++) {
            int current = Math.max(prev1, slotValues[i] + prev2);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int[] slots = {200, 700, 900, 300, 100};
        System.out.println("Max revenue: " + maxRevenue(slots));
    }
}

Max revenue: 1100

How is House Robber different from House Robber II (circular)?

| Aspect | House Robber (Linear) | House Robber II (Circular) |
|---|---|---|
| Layout | Houses in a line | Houses in a circle |
| Constraint | Cannot rob adjacent | Cannot rob adjacent, first and last are also adjacent |
| Solution | Single linear DP pass | Two linear DP passes, take the max |
| Passes | One pass over all houses | Pass 1: exclude last house. Pass 2: exclude first house |

In the circular version, the first and last houses are adjacent, so you cannot rob both. The trick is to run the linear House Robber twice: once on houses 0 through n-2 and once on houses 1 through n-1, then return the larger result.

public static int maxRevenueCircular(int[] slotValues) {
    int n = slotValues.length;
    if (n == 1) return slotValues[0];
    return Math.max(
        maxRevenueRange(slotValues, 0, n - 2),
        maxRevenueRange(slotValues, 1, n - 1)
    );
}

private static int maxRevenueRange(int[] values, int start, int end) {
    int prev2 = 0, prev1 = 0;
    for (int i = start; i <= end; i++) {
        int current = Math.max(prev1, values[i] + prev2);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

What are the edge cases?

Edge cases include empty arrays, single-element arrays, and arrays where all values are equal.

• Empty array – return 0, there is nothing to rob.
• Single house – return its value, no adjacency constraint applies.
• Two houses – return the larger of the two.
• All values equal – the answer is the sum of every other element, roughly n/2 times the value.
• All zeros except one – the answer is that single non-zero value.

// Edge case: two houses
int[] twoSlots = {500, 300};
// dp[0] = 500, dp[1] = max(500, 300) = 500
// Answer: 500 (skip the smaller slot)

What are common mistakes?

The most common mistake is initialising dp[1] incorrectly.

// WRONG: dp[1] = nums[1]
// This ignores the possibility that nums[0] > nums[1]
dp[1] = slotValues[1]; // BUG

// CORRECT: dp[1] = max(nums[0], nums[1])
dp[1] = Math.max(slotValues[0], slotValues[1]);

Another mistake is reaching back to dp[i-2] when i is 1 without handling the base case, causing an index-out-of-bounds error.

What is the time and space complexity?

The array version runs in O(n) time and O(n) space. The rolling-variable version runs in O(n) time and O(1) space. Both make a single pass through the input. For a banking promotion scheduler handling hundreds of time slots, this is instant.

What should a senior engineer know?

A senior engineer should recognise that House Robber is a template for all "non-adjacent selection" problems. The same pattern applies to maximising values on a number line with exclusion zones, job scheduling where consecutive jobs conflict, and selecting non-overlapping intervals.

The recurrence dp[i] = max(dp[i-1], value[i] + dp[i-2]) generalises to dp[i] = max(dp[i-1], value[i] + dp[i-k]) when the exclusion zone is k elements wide instead of one.

// Generalised: cannot select within k positions
public static int maxRevenueWithGap(int[] values, int gap) {
    int n = values.length;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        int skip = (i > 0) ? dp[i - 1] : 0;
        int take = values[i] + ((i > gap) ? dp[i - gap - 1] : 0);
        dp[i] = Math.max(skip, take);
    }
    return dp[n - 1];
}