213. House Robber II

#dp

Problem

House Robber II - LeetCodeLeetCode

Intuition

The inution of the problem is same as 198. House Robber.

Except here it is a extra constraint that it is circular. Which means, we cannot consider the first and last house at same time. So to avoid that, we make the array into two different subarrays

1. O to last but 1 [0 to n-1]

2. 1 to last [1 to n]

Time Complexity

Space Complexity

Solution

class Solution {
    public int rob(int[] nums) {
        // N -> Number of houses/nums.length
        // Time Complexity: O(N) + O(N), to calculate the max value for both the cases
        // Space Complexity: O(1), if we exclude the slicing
        
        // If there is only one house, return its value
        if (nums.length == 1) {
            return nums[0];
        }

        // Divide the problem into two cases:
        // Case 1: Rob houses from index 0 to n-2
        int[] s1 = Arrays.copyOfRange(nums, 0, nums.length - 1);

        // Case 2: Rob houses from index 1 to n-1
        int[] s2 = Arrays.copyOfRange(nums, 1, nums.length);

        // Return the maximum value between the two cases
        return Math.max(helper(s1), helper(s2));
    }

    // Helper function to calculate the maximum amount that can be robbed
    // without adjacent houses being robbed
    private int helper(int[] nums) {
        int n = nums.length;

        int prev2 = 0; // Stores the maximum value till i-2
        int prev1 = nums[0]; // Stores the maximum value till i-1

        // Iterate over the array to calculate the maximum value till each house
        for (int i = 1; i < n; i++) {
            int f1 = nums[i] + prev2; // Rob the current house along with the maximum value till i-2
            int f2 = prev1; // Skip the current house and take the maximum value till i-1
            int current = Math.max(f1, f2); // Choose the maximum value between f1 and f2
            prev2 = prev1; // Update the maximum value till i-2
            prev1 = current; // Update the maximum value till i-1
        }

        // Return the maximum value till the last house
        return prev1;
    }
}