Last updated on October 10th, 2024 at 12:53 am

Here, We see House Robber LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

House Robber LeetCode Solution

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 = [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 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

1. House Robber Leetcode Solution C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size(), pre = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            int temp = max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
};

1.1 Explanation

• Variables: pre keeps track of the maximum money that can be robbed from the houses before the current one, and cur keeps track of the maximum money that can be robbed including the current house.
• Iteration: For each house (nums[i]), calculate the maximum money that can be robbed either by skipping the current house (cur) or by adding the current house value to the money that could be robbed from the houses before it (pre + nums[i]).
• Update: Update pre to cur (previous maximum becomes current excluding current house), and update cur to temp (maximum money including current house).
• Return: Return cur, which holds the maximum money that can be robbed without alerting the police.

1.2 Time Complexity

• O(n), where n is the number of houses (length of nums). The algorithm makes a single pass through the array.

1.3 Space Complexity

• O(1), because only a constant amount of extra space is used regardless of the size of nums.

2. House Robber Leetcode Solution Java

class Solution {
    public int rob(int[] nums) {
        int pre = 0, cur = 0;
        for (int num : nums) {
            final int temp = Integer.max(pre + num, cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
}

2.1 Explanation

• Variables: pre keeps track of the maximum money that can be robbed from the houses before the current one, and cur keeps track of the maximum money that can be robbed including the current house.
• Iteration: For each house (nums[i]), calculate the maximum money that can be robbed either by skipping the current house (cur) or by adding the current house value to the money that could be robbed from the houses before it (pre + nums[i]).
• Update: Update pre to cur (previous maximum becomes current excluding current house), and update cur to temp (maximum money including current house).
• Return: Return cur, which holds the maximum money that can be robbed without alerting the police.

2.2 Time Complexity

• O(n), where n is the number of houses (length of nums). The algorithm makes a single pass through the array.

2.3 Space Complexity

• O(1), because only a constant amount of extra space is used regardless of the size of nums.

3. House Robber Leetcode Solution JavaScript

var rob = function(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);
    
    let maxAtTwoBefore = nums[0];
    let maxAtOneBefore = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < nums.length; i++) {
        const maxAtCurrent = Math.max(nums[i] + maxAtTwoBefore, maxAtOneBefore);
        
        maxAtTwoBefore = maxAtOneBefore;
        maxAtOneBefore = maxAtCurrent;
    }
    return maxAtOneBefore;
};

3.1 Explanation

• This JavaScript code uses a dynamic programming approach to solve the problem of finding the maximum money that can be robbed without alerting the police.

3.2 Time Complexity

• O(n), where n is the number of houses (length of nums). Similar to the previous implementations, it iterates through the array once.

3.3 Space Complexity

• O(1), because it only uses a constant amount of extra space.

4. House Robber Leetcode Solution Python

class Solution(object):
    def rob(self, 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)

4.1 Explanation

• This Python code uses a similar dynamic programming approach to calculate the maximum money that can be robbed without alerting the police.

4.2 Time Complexity

• O(n), where n is the number of houses (length of nums). It iterates through the list once.

4.3 Space Complexity

• O(1), because only a constant amount of extra space is used.