algoadvance

Leetcode 213. House Robber II

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 an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Clarifying Questions

1. Q: What is the length of the array nums? A: The length of the array is between 1 and 100.

2. Q: Can the elements of the array nums be negative? A: No, elements of nums represent the amount of money in each house and will be non-negative.

3. Q: What should the function return if nums is empty? A: Since the problem guarantees at least one house, we don’t need to handle an empty nums. If there was an empty situation, it should return 0.

Strategy

To handle the circular arrangement of houses, we need to consider two scenarios:

1. Robbing houses from the first house to the second last house.
2. Robbing houses from the second house to the last house.

We then find the maximum from these two scenarios. This approach leverages the original “House Robber I” problem and modifies it to fit the circular house arrangement constraint.

Steps:

1. Define a helper function for the “House Robber I” problem which calculates the maximum amount for a linear range of houses.
2. Use this helper function to calculate the maximum from the two scenarios mentioned.
3. Return the maximum of these two results.

Code

#include <vector>
#include <algorithm>

using namespace std;

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

        // Helper to calculate the maximum robbery amount for a linear sequence of houses
        auto robLinear = [](vector<int>& houses) -> int {
            int rob1 = 0, rob2 = 0;
            for (int money : houses) {
                int newRob = max(rob1 + money, rob2);
                rob1 = rob2;
                rob2 = newRob;
            }
            return rob2;
        };

        vector<int> nums1(nums.begin(), nums.end() - 1);
        vector<int> nums2(nums.begin() + 1, nums.end());

        return max(robLinear(nums1), robLinear(nums2));
    }
};

Time Complexity

• Time Complexity: O(N), where N is the number of houses. This is because each “robLinear” function call processes each house once in its respective sub-array.
• Space Complexity: O(1). No extra space is used other than a few variables for storing intermediate results.

Explanation

1. The rob function handles the special case where there’s only one house.
2. The robLinear lambda function computes the solution for the linear (non-circular) house robbery problem using dynamic programming.
3. We create two subarrays: nums1 excludes the last house and nums2 excludes the first house.
4. We compute the result for both subarrays and return the maximum value.

This solution efficiently solves the problem while maintaining clear and manageable logic.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?