213. House Robber II

Medium

Problem Description

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.

Examples

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.

Example 3:
Input: nums = [1,2,3]
Output: 3
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    def rob_line(arr: List[int]) -> int:
        if not arr:
            return 0
        if len(arr) == 1:
            return arr[0]
        
        dp = [0] * len(arr)
        dp[0] = arr[0]
        dp[1] = max(arr[0], arr[1])
        
        for i in range(2, len(arr)):
            dp[i] = max(dp[i-1], dp[i-2] + arr[i])
        
        return dp[-1]
    
    # Rob houses 0 to n-2 or houses 1 to n-1
    return max(rob_line(nums[:-1]), rob_line(nums[1:]))

Space-Optimized Solution:


def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    def rob_line(arr: List[int]) -> int:
        rob1, rob2 = 0, 0
        
        for num in arr:
            temp = max(rob1 + num, rob2)
            rob1 = rob2
            rob2 = temp
        
        return rob2
    
    return max(rob_line(nums[:-1]), rob_line(nums[1:]))

Java Solution


class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        
        return Math.max(robLine(nums, 0, nums.length - 2),
                       robLine(nums, 1, nums.length - 1));
    }
    
    private int robLine(int[] nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = Math.max(rob1 + nums[i], rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        
        return rob2;
    }
}

C++ Solution


class Solution {
public:
    int rob(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() == 1) {
            return nums[0];
        }
        
        return max(robLine(nums, 0, nums.size() - 2),
                  robLine(nums, 1, nums.size() - 1));
    }
    
private:
    int robLine(const vector& nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = max(rob1 + nums[i], rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        
        return rob2;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (!nums.length) {
        return 0;
    }
    if (nums.length === 1) {
        return nums[0];
    }
    
    const robLine = (start, end) => {
        let rob1 = 0, rob2 = 0;
        
        for (let i = start; i <= end; i++) {
            const temp = Math.max(rob1 + nums[i], rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        
        return rob2;
    };
    
    return Math.max(robLine(0, nums.length - 2),
                   robLine(1, nums.length - 1));
};

C# Solution


public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        if (nums.Length == 1) {
            return nums[0];
        }
        
        return Math.Max(RobLine(nums, 0, nums.Length - 2),
                       RobLine(nums, 1, nums.Length - 1));
    }
    
    private int RobLine(int[] nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = Math.Max(rob1 + nums[i], rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        
        return rob2;
    }
}

Complexity Analysis

Solution Explanation

This problem is a variation of House Robber I with a circular arrangement:

Key Points

Common Pitfalls

Edge Cases