algoadvance

Leetcode 198. 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 constraint stopping you from robbing each of them is that adjacent houses have security systems 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.

Example:

Example 1:

• 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 2:

• Input: nums = [2,7,9,3,1]
• Output: 12
• Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

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

Clarifying Questions:

1. What should be the output if nums is empty?
   • Based on the constraints, nums will always have at least one house.
2. Can two houses have the same amount of money?
   • Yes, there can be multiple houses with the same amount of money.

Strategy:

This problem is typical of the dynamic programming category, where we need to decide for each house whether to rob it or not based on previous decisions:

1. Create an array dp where dp[i] represents the maximum amount of money that can be robbed up to the i-th house.
2. The base cases would be straightforward:
   • dp[0] = nums[0] (Only one house to rob).
   • dp[1] = max(nums[0], nums[1]) (For two houses, take the maximum of robbing the first house or the second).
3. For each subsequent house i (from 2 to n-1), the decision would be:
   • Either rob the current house and add it to the best solution excluding the previous house: nums[i] + dp[i-2].
   • Or not rob the current house and take the best solution up to the previous house: dp[i-1].
4. The formula thus becomes dp[i] = max(dp[i-1], nums[i] + dp[i-2]).

Finally, the answer will be stored in dp[n-1], where n is the length of the nums array.

Code:

#include <vector>
#include <algorithm>

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

        int n = nums.size();
        std::vector<int> dp(n, 0);

        // Base cases
        dp[0] = nums[0];
        dp[1] = std::max(nums[0], nums[1]);

        // Fill the dp array
        for (int i = 2; i < n; ++i) {
            dp[i] = std::max(dp[i-1], nums[i] + dp[i-2]);
        }

        return dp[n-1];
    }
};

Time Complexity:

• Time Complexity: (O(n)), where (n) is the number of houses. We have to traverse the whole list once.
• Space Complexity: (O(n)) due to the dp array used for storing intermediate results. This can be optimized to (O(1)) by using two variables instead of the whole array since we only need the last two results.

This implementation ensures that we are efficiently calculating the optimal robbery amount without violating the constraints of the problem.

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?