LeetCode Medium Challenge Day 24 | House Robber II

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 are 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.

Explanation

The key challenge in this problem is that the houses are arranged in a circular manner, which means the first and last houses are neighbors. Due to this circular arrangement, if you rob the first house, you cannot rob the last house, and vice versa.

To solve this problem, we break it down into two simpler subproblems:

1. Robbing houses excluding the first house: This means you consider the array from the second house to the last house.
2. Robbing houses excluding the last house: This means you consider the array from the first house to the second-last house.

The result is the maximum of the two scenarios.

The helper function helper(int[] nums) calculates the maximum amount of money that can be robbed for a linear arrangement of houses using dynamic programming

Explanation of the Code

1. Edge Cases: The code first checks if there are no houses (nums.length == 0) or just one house (nums.length == 1). If there's only one house, the solution is simply the amount of money in that house.
2. Divide the Problem: The main problem is divided into two subproblems: robbing the houses from the second to the last (nums[1...n-1]) and robbing from the first to the second-last (nums[0...n-2]). These are handled by the helper function.
3. Helper Function: The helper function uses dynamic programming to calculate the maximum amount of money that can be robbed from a linear sequence of houses. The approach uses two variables (money1 and money2) to keep track of the maximum money that can be robbed from even and odd indexed houses.
4. Result: The final result is the maximum of the two subproblems, which is returned as the solution to the circular problem.

CODE

class Solution {
    public int rob(int[] nums) {
        // Edge case: If there's only one house or no houses
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }

        // Calculate the maximum profit by either excluding the first or the last house
        int result1 = helper(Arrays.copyOfRange(nums, 1, nums.length));
        int result2 = helper(Arrays.copyOfRange(nums, 0, nums.length - 1));
        
        // Return the maximum of both scenarios
        return Math.max(result1, result2);
    }

    int helper(int[] nums) {
        int money1 = 0;
        int money2 = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                money1 += nums[i];
                money1 = Math.max(money1, money2);
            } else {
                money2 += nums[i];
                money2 = Math.max(money1, money2);
            }
        }

        // Return the maximum amount of money that can be robbed
        return Math.max(money1, money2);
    }
}