House Robber II

Problem Statement

The stakes are higher! Houses are now in a circle, so robbing the first and last houses together is off-limits. Maximize your loot without tripping the alarm. This medium-level DP twist adds a circular conundrum—plan your robbery with care!

Example

Input: nums = [2, 3, 2]

Output: 3 (rob 3)

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

Output: 4 (rob 1+3)

Input: nums = [1, 2, 3]

Output: 3 (rob 3)

Code

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(robRange(nums, 0, nums.length-2), robRange(nums, 1, nums.length-1));
    }
    private int robRange(int[] nums, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = curr;
            curr = Math.max(prev + nums[i], curr);
            prev = temp;
        }
        return curr;
    }
}
            

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    return max(rob_range(nums, 0, len(nums)-2), rob_range(nums, 1, len(nums)-1))

def rob_range(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(prev + nums[i], curr)
    return curr

# Example usage
print(rob([2, 3, 2]))  # 3
print(rob([1, 2, 3, 1]))  # 4
            

function rob(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    return Math.max(robRange(nums, 0, nums.length-2), robRange(nums, 1, nums.length-1));
}

function robRange(nums, start, end) {
    let prev = 0, curr = 0;
    for (let i = start; i <= end; i++) {
        [prev, curr] = [curr, Math.max(prev + nums[i], curr)];
    }
    return curr;
}

// Example usage
console.log(rob([2, 3, 2]));  // 3
console.log(rob([1, 2, 3, 1]));  // 4
            

Explanation

• DP Insight: Solve two cases: exclude first house or exclude last house, take max.
• Steps: Use a helper to rob a range, tracking max loot with two variables.
• Flow Example ([1,2,3,1]): Exclude first: 3, Exclude last: 4 (1+3)—pick 4.
• Why It Works: Circular constraint splits problem into linear subproblems.

Note