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 security systems 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 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 problem can be broken down into two subproblems because of the circular arrangement:

1. Robbing houses from index 0 to n-2: Treat the array as if the last house (n-1) doesn't exist.
2. Robbing houses from index 1 to n-1: Treat the array as if the first house (0) doesn't exist.

The maximum amount we can rob is the larger of the results from these two subproblems. Each subproblem is a standard "House Robber" problem (LeetCode 198) which can be solved using dynamic programming.

Explanation

The dynamic programming approach for the standard House Robber problem works by creating a DP array where dp[i] represents the maximum amount of money that can be robbed up to house i. The recurrence relation is:

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

This means at house i, we can either:

• Not rob it, and take the maximum amount from the previous houses (dp[i-1]).
• Rob it, adding its value to the maximum amount from two houses before (dp[i-2] + nums[i]).

We apply this logic to both subproblems and return the maximum of the two results.

Code

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        //Rob from index 0 to n-2
        int[] dp1 = new int[n];
        dp1[0] = nums[0];
        dp1[1] = Math.Max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.Max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        int rob1 = dp1[n-2];


        //Rob from index 1 to n-1
        int[] dp2 = new int[n];
        dp2[0] = nums[1];
        if (n > 2) dp2[1] = Math.Max(nums[1], nums[2]);
        for (int i = 2; i < n -1; i++) {
            dp2[i] = Math.Max(dp2[i - 1], dp2[i - 2] + nums[i+1]);
        }
        int rob2 = (n>1)? dp2[n-2]:nums[1];


        return Math.Max(rob1, rob2);
    }
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the array twice.
• Space Complexity: O(n) in the worst case due to the DP arrays. This could be optimized to O(1) by using only a few variables to store the necessary DP values instead of full arrays.