Is House Robber easy or hard?

House Robber is rated Medium because the recurrence is simple once recognized, but many beginners struggle to model the decision process. Understanding how to convert the recurrence into an iterative dynamic programming solution is the key challenge.

House Robber Python/Java solution

Python and Java implementations both follow the same DP recurrence: max(prev1, prev2 + nums[i]). Iterate through the array, update the rolling states, and return the final maximum. The logic remains identical across Python, Java, C++, C#, and JavaScript.

How to solve House Robber in O(n)?

Use dynamic programming and process the houses from left to right. At each index, compute the best result by choosing between skipping the house (previous maximum) or robbing it (value plus result two houses back). This single pass produces an O(n) time solution with either O(n) or O(1) space depending on the implementation.

What is the best approach for House Robber?

The best approach uses dynamic programming with a rolling state. Track the maximum money up to the previous house and the house before that, then compute the current best using max(prev1, prev2 + nums[i]). This runs in O(n) time and O(1) space and is the solution most interviewers expect.

Is House Robber asked at Google/Amazon/Meta?

House Robber and its variations appear frequently in interviews at companies like Amazon, Google, Meta, and Microsoft. The problem tests dynamic programming fundamentals, especially recognizing optimal substructure and converting a recurrence into an efficient iterative solution.

What data structure is used in House Robber?

The solution primarily uses arrays and dynamic programming state variables. The DP array stores the best result for each house index, while the optimized version replaces the array with two variables that track previous results.

What is the time complexity of House Robber?

The optimal solution runs in O(n) time because you iterate through the list of houses once. Each step performs a constant amount of work to decide whether to rob or skip the current house. Space complexity can be reduced to O(1) using two variables.

Description Solution Video 32:23

198. House Robber

Medium53.6% acceptance40 companies

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.

Constraints: