House Robber II medium

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers nums representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

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.

Steps

The key insight is to realize that because the houses are in a circle, robbing the first house automatically prevents robbing the last house, and vice-versa. We can solve this by considering two separate subproblems:

1. Robbing houses from index 0 to n-2: This subproblem is a standard House Robber problem (without the circular constraint).
2. Robbing houses from index 1 to n-1: This is also a standard House Robber problem.

The maximum amount we can rob will be the maximum of the results from these two subproblems.

Explanation

The standard House Robber problem (without the circular constraint) can be solved using dynamic programming. We create a dp array where dp[i] represents the maximum amount we can rob considering houses up to index i. The recurrence relation is:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

This means we either rob the current house (dp[i-2] + nums[i]) or we don't (dp[i-1]). We initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).

We apply this twice: once for the range [0, n-2] and once for the range [1, n-1]. The maximum of the two results is our final answer.

Code

#include <vector>
#include <algorithm>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    // Rob houses from index 0 to n-2
    vector<int> dp1(n, 0);
    dp1[0] = nums[0];
    dp1[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n - 1; ++i) {
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
    }

    // Rob houses from index 1 to n-1
    vector<int> dp2(n, 0);
    dp2[1] = nums[1];
    if (n > 2) dp2[2] = max(nums[1], nums[2]);
    for (int i = 3; i < n; ++i) {
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
    }

    return max(dp1[n - 2], dp2[n - 1]);
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the array twice.
• Space Complexity: O(n), due to the dp arrays. This can be optimized to O(1) by using only a few variables to track the maximum values instead of full arrays. (See optimized code below)

Optimized Code (O(1) space):

#include <vector>
#include <algorithm>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    int rob1 = nums[0], rob2 = max(nums[0], nums[1]);

    for (int i = 2; i < n -1; ++i) {
        int temp = max(rob2, rob1 + nums[i]);
        rob1 = rob2;
        rob2 = temp;
    }
    int ans1 = rob2;

    rob1 = nums[1];
    if(n>2) rob2 = max(nums[1],nums[2]);

    for(int i=3;i<n;++i){
        int temp = max(rob2, rob1+nums[i]);
        rob1 = rob2;
        rob2 = temp;
    }

    return max(ans1,rob2);
}

This optimized version achieves the same functionality with constant space complexity. It cleverly reuses variables to track only the necessary information at each step.