House Robber II

Rob houses but adjacent houses can't be robbed, also first and last houses are adjacent to each other

House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only thing stopping you from robbing every house is that adjacent houses have connected security systems — if two adjacent houses are broken into on the same night, the police will automatically be alerted.

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

Examples

Example 1

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

Output: 4

Explanation: Rob house 1 (money = 1), then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 2

Input: nums = [2, 7, 9, 3, 1]

Output: 12

Explanation: Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1). Total = 2 + 9 + 1 = 12.

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400

Important note before the solution: The problem statement above describes houses in a straight line — there's no mention of the street being a circle, and house 0 and the last house are not neighbors of each other. However, all four solutions below use an excludeFirst / excludeLast technique. That technique belongs to a different, related problem — often called "House Robber II" — where the houses are arranged in a circle, and the first and last house count as neighbors of each other.

Applying that circular technique here is a bug: it forbids ever robbing both the first house and the last house together, even though in a straight line, they aren't neighbors and robbing both is often exactly the right answer. You can see this fail on Example 2 above: nums = [2, 7, 9, 3, 1] should give 12 (which robs both house 0 and house 4), but running the code below on this input actually gives 11, since it never considers a solution using both ends.

If you want the code to correctly solve the linear version of this problem (as stated above), you don't need the excludeFirst / excludeLast split at all — a single pass computing the maximum sum of non-adjacent elements across the whole array (like the earlier "Maximum Sum of Non-Adjacent Elements" solution) is enough. The excludeFirst / excludeLast approach shown below should only be used if the street is actually circular.

Solution (As Provided — Written for a Circular Street)

Brute Force

The approach explores two possibilities: one where house 0 is excluded, and one where the last house is excluded. Within each possibility, at every index we either take the current house (adding it to the result from two indices back) or skip it (taking the result from one index back), returning whichever is larger.

var rob = function(nums) {
    let n = nums.length;
    function recurr(index, start) {
        if (start > index) {
            return 0;
        }

        if (start == index) {
            return nums[start];
        }

        let skip = recurr(index - 1, start);
        let take = nums[index] + recurr(index - 2, start);

        return Math.max(skip, take);
    }

    const excludeFirst = recurr(n - 1, 1);
    const exculdeLast = recurr(n - 1, 0);

    return Math.max(excludeFirst, exculdeLast);
};

Memoization

The same logic as above, but with two separate memo arrays — one for each of the two starting possibilities — since a given index's result depends on which possibility we're currently exploring.

var rob = function (nums) {
    let n = nums.length;
    let memo1 = [];
    let memo2 = [];

    function recurr(index, start, memo) {
        if (start > index) {
            return 0;
        }

        if (start == index) {
            return nums[start];
        }

        if (memo[index] !== undefined) {
            return memo[index];
        }

        let skip = recurr(index - 1, start, memo);
        let take = nums[index] + recurr(index - 2, start, memo);

        memo[index] = Math.max(skip, take);
        return memo[index];
    }

    const excludeFirst = recurr(n - 1, 1, memo1);
    const exculdeLast = recurr(n - 1, 0, memo2);

    return Math.max(excludeFirst, exculdeLast);
};

Tabulation

Instead of recursing, we build the answer forward, one index at a time, within each of the two possibilities.

var rob = function (nums) {
    let n = nums.length;

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

    function recurr(end, start) {
        let memo = Array(n).fill(0);

        memo[start] = nums[start];

        for (let i = start + 1; i <= end; i++) {

            let skip = memo[i - 1];
            let previous = 0;
            if (i - 2 >= start) {
                previous = memo[i - 2];
            }

            let pick = nums[i] + previous;

            memo[i] = Math.max(pick, skip);
        }

        return memo[end];
    }

    const excludeFirst = recurr(n - 1, 1);
    const excludeLast = recurr(n - 2, 0);

    return Math.max(excludeFirst, excludeLast);
};

Space Optimization

Since each step only needs the results from the previous two indices, we can track those with two variables instead of a full array.

var rob = function (nums) {
    let n = nums.length;

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

    function recurr(end, start) {
        let prev1 = nums[start];
        let prev2 = 0;

        for (let i = start + 1; i <= end; i++) {

            let skip = prev1;
            let previous = 0;
            if (i - 2 >= start) {
                previous = prev2;
            }

            let pick = nums[i] + previous;

            prev2 = prev1;
            prev1 = Math.max(pick, skip);
        }

        return prev1;
    }

    const excludeFirst = recurr(n - 1, 1);
    const excludeLast = recurr(n - 2, 0);

    return Math.max(excludeFirst, excludeLast);
};