LeetCode 198: House Robber Solution

Master LeetCode problem 198 (House Robber), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

198. House Robber

Medium

Array Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming to keep track of the maximum amount of money we can rob up to the ith house without alerting the police. We can define a DP array where dp[i] represents the maximum amount of money that can be robbed up to the ith house.

The key idea is to consider whether to rob the current house or not. If we choose to rob the current house, then the maximum amount we can rob up to the ith house is the money in the current house plus the maximum amount we could rob up to the (i-2)th house. This is because we cannot rob adjacent houses due to the security system. If we choose not to rob the current house, then the maximum amount we can rob up to the ith house is the same as the maximum amount we could rob up to the (i-1)th house.

We can then iterate through the houses and update the DP array accordingly. Finally, the answer will be the maximum amount of money we can rob up to the last house.

Time Complexity: O(n) where n is the number of houses. Space Complexity: O(n) for the DP array.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 198 (House Robber)?

This page provides optimized solutions for LeetCode problem 198 (House Robber) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 198 (House Robber)?

The time complexity for LeetCode 198 (House Robber) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 198 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 198 in Java, C++, or Python.

Back to LeetCode Solutions