Last updated on January 13th, 2025 at 09:34 pm

Here, we see a House Robber II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Microsoft

Level of Question

Medium

House Robber II LeetCode Solution

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

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Dynamic Programming”. Specifically, this problem is a variation of the “0/1 Knapsack” problem. The goal is to maximize the sum of non-adjacent elements in the array, which is achieved by making decisions at each step: either include the current house’s value or skip it.

3. Code Implementation in Different Languages

3.1 House Robber II C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size(); 
        if (n < 2) return n ? nums[0] : 0;
        return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
    }
private:
    int robber(vector<int>& nums, int l, int r) {
        int pre = 0, cur = 0;
        for (int i = l; i <= r; i++) {
            int temp = max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
};

3.2 House Robber II Java

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length < 2)
            return nums[0];
        
        int[] startFromFirstHouse = new int[nums.length + 1];
        int[] startFromSecondHouse = new int[nums.length + 1];
        
        startFromFirstHouse[0]  = 0;
        startFromFirstHouse[1]  = nums[0];
        startFromSecondHouse[0] = 0;
        startFromSecondHouse[1] = 0;
        
        for (int i = 2; i <= nums.length; i++) {
            startFromFirstHouse[i] = Math.max(startFromFirstHouse[i - 1], startFromFirstHouse[i - 2] + nums[i-1]);
            startFromSecondHouse[i] = Math.max(startFromSecondHouse[i - 1], startFromSecondHouse[i - 2] + nums[i-1]);
        }
        
        return Math.max(startFromFirstHouse[nums.length - 1], startFromSecondHouse[nums.length]);
    }
}

3.3 House Robber II JavaScript

var rob = function(nums) {
    if (nums.length < 2) {
        return nums[0] || 0;
    }
    const memo1 = [nums[0]];
    const memo2 = [0, nums[1]];
    for (let i=1; i<nums.length - 1; i++) {
        memo1[i] = Math.max(nums[i] + (memo1[i - 2] || 0), memo1[i - 1]);
    }
    for (let i=2; i<nums.length; i++) {
        memo2[i] = Math.max(nums[i] + memo2[i - 2], memo2[i - 1]);
    }
    return Math.max(memo1.pop(), memo2.pop());
};

3.4 House Robber II Python

class Solution(object):
    def rob(self, nums):
        def simple_rob(nums):
            rob, not_rob = 0, 0
            for num in nums:
                rob, not_rob = not_rob + num, max(rob, not_rob)
            return max(rob, not_rob)
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]
        else:
            return max(simple_rob(nums[1:]), simple_rob(nums[:-1]))

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(1)

• The problem is solved using Dynamic Programming with a focus on maximizing the sum of non-adjacent elements.
• The circular nature of the problem is handled by splitting it into two subproblems.
• Python and C++ implementations are more space-efficient (O(1)) compared to Java and JavaScript (O(n)).