algoadvance

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

Clarifying Questions:

  1. Q: What should be returned if the nums array is empty? A: Return 0 since there are no houses to rob.
  2. Q: What should be returned if nums contains only one house? A: Return the value of the single element since it represents the only house present.
  3. Q: Can nums have non-integer or negative values? A: No, nums is specified to hold non-negative integers only.

Strategy:

The problem can be viewed as a variation of the House Robber I problem but with the added complexity of the houses being in a circle. The key to solving this problem is to handle it as two separate linear House Robber problems:

  1. Rob houses from index 0 to n-2 - ignoring the last house.
  2. Rob houses from index 1 to n-1 - ignoring the first house.

The solution will be the maximum amount robbed from the above two scenarios.

Code:

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // Helper function to perform the simple robbing along a line (House Robber I)
        return Math.max(robLinear(nums, 0, nums.length - 2), robLinear(nums, 1, nums.length - 1));
    }

    private int robLinear(int[] nums, int start, int end) {
        int prev1 = 0, prev2 = 0;
        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 2};
        System.out.println(solution.rob(nums));  // Output: 3
        
        nums = new int[]{1, 2, 3, 1};
        System.out.println(solution.rob(nums));  // Output: 4
        
        nums = new int[]{0};
        System.out.println(solution.rob(nums));  // Output: 0
    }
}

Time Complexity:

The time complexity for this solution is O(n) where n is the number of houses. This is because both scenarios (rob from 0 to n-2 and rob from 1 to n-1) each take linear time to calculate, leading to an overall linear time complexity.

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