algoadvance

Leetcode 198. House Robber Sure, let’s work on the LeetCode problem 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 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.

Clarifying Questions

  1. Q: Can nums be empty? A: Yes, if nums is empty, the expected return value is 0.

  2. Q: What should be done if nums has only one house? A: If nums has only one house, the maximum amount you can rob is the value of that house.

Strategy

  1. Dynamic Programming Approach: To decide whether to rob the current house, compare:
    • Not robbing the current house, and hence taking the max rob amount up to the previous house.
    • Robbing the current house, and hence combining the current house value with the max rob amount up to the house before the previous one.
  2. DP Array: Create a dp array where dp[i] represents the maximum amount of money that can be robbed from the first house to the i-th house.

Code

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[n-1];
    }
}

Time Complexity

The time complexity of the provided solution is O(n), where n is the number of houses. This is because we only iterate through the array once.

The space complexity is also O(n) due to the dp array. This can be optimized to O(1) if we only keep track of the last two states, but as it stands, the current solution is clear and easy to understand.

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