House Robber II

Problem Statement

You are a professional thief who targets a neighborhood where houses are arranged in a circular fashion. In this setup, the first house is directly adjacent to the last house, forming a closed loop. Each house has a certain amount of money stashed, and your challenge is to steal as much as you can. However, there's a catch: the houses have a state-of-the-art security system. If you rob two adjacent houses in one night, the security system will detect the activity and immediately alert the police. Given an integer array nums, which represents the amount of money in each house, your task is to determine the maximum amount of money you can rob without triggering any alarms.

Examples

Example 1

Input:

nums = [2,3,2]

Output:

3

Explanation:

You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2

Input:

nums = [1,2,3,1]

Output:

4

Explanation:

Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3

Input:

nums = [1,2,3]

Output:

3

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Approach and Intuition

The problem presents an interesting twist on the classic "house robber" problem by introducing a circular arrangement of houses. Here's how you can think about solving it while maintaining the constraints:

1. Understanding the problem:

   • If you rob the first house (nums[0]), then you cannot rob the last house (nums[length-1]), as they are adjacent in a circular list.
   • Deciding not to rob the first house means you can consider robbing from the second house to the last.
   • Essentially, the problem can be broken down into two separate scenarios:
     • Rob houses from index 0 to length-2.
     • Rob houses from index 1 to length-1.

2. Approach to solve:

   • Utilize dynamic programming to solve for the maximum amount robbable from a linear set of houses.
   • Define a function that calculates the maximum rob-able amount for a linear list of houses.
   • Use this function on the two scenarios described:
     • From the first house to the second-last.
     • From the second house to the last.

3. Implementation steps:

   • Define a helper function, say robLinear(houses), which implements the robbery logic on a linear list of houses. This would typically involve iterating over the houses while maintaining two variables that track the maximum amounts rob-able with and without robbing the current house.
   • Use this helper function twice as per the cases derived:
     • Once for the sublist excluding the last house.
     • Once for the sublist excluding the first house.
   • The final result will be the maximum value obtained from these two function calls.

This approach leverages the technique of breaking down the problem into simpler subproblems (linear vs circular), a hallmark of dynamic programming. This ensures that the solution is both efficient and comprehensive while adhering to the imposed constraint of a circular arrangement.

Solutions

class Solution {
public:
    int houseRobber(vector<int>& houses) {
        if (houses.size() == 0) return 0;
    
        if (houses.size() == 1) return houses[0];
    
        int rob1 = robRange(houses, 0, houses.size() - 2);
        int rob2 = robRange(houses, 1, houses.size() - 1);
    
        return max(rob1, rob2);
    }
    
private:
    int robRange(vector<int>& houses, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; ++i) {
            int temp = curr;
            curr = max(houses[i] + prev, curr);
            prev = temp;
        }
    
        return curr;
    }
};