Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

House Robber solution and explanation

MediumArrayDynamic Programming7 min read53.6% acceptanceUpdated 9 Apr 2026
Asked atCiscoAgodaGrabCars24FreechargeEnvoy
+14 moreDatabricksTiktokInfosysNVIDIAPhonePeAirbnbExpediaZetaGoogleAmazonMicrosoftMetaBloombergTCS
Practise House Robber
32:23
DP 5. Maximum Sum of Non-Adjacent Elements | House Robber | 1-D | DP on Subsequencestake U forward · 32:23 · 732K viewsWatch on YouTube
9 more videos on this problem
  1. DP 5. Maximum Sum of Non-Adjacent Elements | House Robber | 1-D | DP on Subsequencestake U forward · 32:23 · 732K views
  2. House Robber - Leetcode 198 - Python Dynamic ProgrammingNeetCode · 10:35 · 474K views
  3. House Robber (LeetCode 198) | Full solution with diagrams | Easy explanation | Study AlgorithmsNikhil Lohia · 14:31 · 72K views
  4. LeetCode 198. House Robber (Algorithm Explained)Nick White · 13:25 · 60K views
  5. House Robber | Recursion | Memo | Bottom Up | Leetcode 198codestorywithMIK · 29:51 · 48K views
  6. House Robber - Leetcode 198 - Dynamic Programming (Python)Greg Hogg · 13:15 · 28K views
  7. House Robber | LeetCode 198 | Google Coding Interview TutorialTerrible Whiteboard · 9:38 · 10K views
  8. House Robber | Live Coding with Explanation | Leetcode - 198Algorithms Made Easy · 8:01 · 8K views
  9. LeetCode Solution - 198 House Robber | Javascript | Dynamic ProgrammingThinkFWD · 17:52 · 5K views
  10. House Robber | Leet code 198 | Theory explained + Python codeSai Anish Malla · 12:12 · 2K views

The problem

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:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Approach overview

Problem Overview: You are given an array where each element represents money stored in a house along a street. Adjacent houses cannot be robbed on the same night because they trigger an alarm. The goal is to compute the maximum amount of money you can steal without robbing two neighboring houses.

Approach 1: Dynamic Programming - Iterative DP Array (O(n) time, O(n) space)

This problem fits the classic dynamic programming pattern where each decision depends on previous optimal results. Define dp[i] as the maximum money you can rob from the first i houses. For each house, you either rob it or skip it. If you rob house i, you add its value to dp[i-2]. If you skip it, you keep dp[i-1]. The recurrence becomes dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Iterate through the array, computing the best outcome at each step.

This approach explicitly stores results for every house, making the logic easy to visualize and debug. It clearly shows how the problem reduces to choosing between two previous states. The tradeoff is extra memory proportional to the number of houses.

Approach 2: Dynamic Programming - Optimized Space (O(n) time, O(1) space)

The DP recurrence only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of maintaining a full array, keep two variables representing these values. As you iterate through the houses, compute the current best value and shift the variables forward.

At each step, calculate current = max(prev1, prev2 + num), where prev1 stores the best result up to the previous house and prev2 stores the best result two houses back. Update the variables as you move forward. This keeps the same decision logic while eliminating the DP array.

This version is the standard optimal solution discussed in interviews. It still performs a single pass through the array and maintains constant memory usage. The algorithm behaves like a rolling dynamic programming window that tracks only the necessary states.

Recommended for interviews: Start by explaining the DP recurrence using the array-based solution since it clearly demonstrates the decision process between robbing and skipping a house. Then optimize it to the constant-space version. Interviewers usually expect the O(n) time, O(1) space solution because it shows strong understanding of dynamic programming state transitions and space optimization.

Approach 1: Dynamic Programming - Iterative Approach

This approach uses a dynamic programming table, where we maintain an array 'dp' such that dp[i] represents the maximum amount of money that can be robbed up to house i. We iterate through the list of houses and for each house, decide whether to rob it or skip it, based on the previous results stored in the dp table.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

nums = [2, 7, 9, 3, 1]
print("Max amount that can be robbed:", rob(nums))
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length-1];
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println("Max amount that can be robbed: " + sol.rob(nums));
    }
}
#include <iostream>
#include <vector>
using namespace std;

int rob(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];
    
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    
    for (int i = 2; i < nums.size(); ++i) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp.back();
}

int main() {
    vector<int> nums = {2, 7, 9, 3, 1};
    cout << "Max amount that can be robbed: " << rob(nums) << endl;
    return 0;
}
function rob(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    
    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp[nums.length - 1];
}

const nums = [2, 7, 9, 3, 1];
console.log("Max amount that can be robbed:", rob(nums));
#include <stdio.h>
#include <string.h>

int rob(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    
    int dp[numsSize];
    memset(dp, 0, sizeof(dp));
    
    dp[0] = nums[0];
    dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];
    
    for (int i = 2; i < numsSize; ++i) {
        dp[i] = (dp[i-1] > dp[i-2] + nums[i]) ? dp[i-1] : dp[i-2] + nums[i];
    }
    
    return dp[numsSize-1];
}

int main() {
    int nums[] = {2, 7, 9, 3, 1};
    int result = rob(nums, sizeof(nums)/sizeof(nums[0]));
    printf("Max amount that can be robbed: %d\n", result);
    return 0;
}
using System;
class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        
        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.Length; i++) {
            dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.Length-1];
    }

    static void Main() {
        int[] nums = {2, 7, 9, 3, 1};
        Solution sol = new Solution();
        Console.WriteLine("Max amount that can be robbed: " + sol.Rob(nums));
    }
}

Using a list 'dp' in Python where each element keeps the computed maximum value of money that can be robbed when considering the list of money up to that index. A choice is made at each house point to maximize profit.

Complexity

Time Complexity: O(n) - The full list is iterated through.
Space Complexity: O(n) - Using a list to keep track of current states.

Try this approach in the editor

Approach 2: Dynamic Programming - Optimized Space Approach

This approach optimizes the space complexity by not using a separate array for storing results of subproblems. Instead, we use two variables to keep track of the maximum amount that can be robbed up to the last two houses considered. This eliminates the need for an auxiliary array and reduces space complexity to O(1).

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev1, prev2 = 0, 0
    for num in nums:
        temp = prev1
        prev1 = max(prev2 + num, prev1)
        prev2 = temp
    return prev1

nums = [2, 7, 9, 3, 1]
print("Max amount that can be robbed:", rob(nums))
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int prev1 = 0, prev2 = 0, current = 0;
        
        for (int num : nums) {
            int temp = current;
            current = Math.max(prev1 + num, prev2);
            prev1 = prev2;
            prev2 = temp;
        }
        return current;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println("Max amount that can be robbed: " + sol.rob(nums));
    }
}
#include <iostream>
#include <vector>
using namespace std;

int rob(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];
    
    int prev1 = nums[0], prev2 = 0, current = nums[0];
    
    for (size_t i = 1; i < nums.size(); ++i) {
        current = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

int main() {
    vector<int> nums = {2, 7, 9, 3, 1};
    cout << "Max amount that can be robbed: " << rob(nums) << endl;
    return 0;
}
function rob(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    
    let prev1 = 0, prev2 = 0, current = 0;
    
    for (let num of nums) {
        let temp = prev1;
        prev1 = Math.max(prev2 + num, prev1);
        prev2 = temp;
    }
    return prev1;
}

const nums = [2, 7, 9, 3, 1];
console.log("Max amount that can be robbed:", rob(nums));
#include <stdio.h>

int rob(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    
    int prev2 = nums[0];
    int prev1 = (nums[1] > nums[0]) ? nums[1] : nums[0];
    int current = prev1;
    
    for (int i = 2; i < numsSize; ++i) {
        current = (prev1 > prev2 + nums[i]) ? prev1 : prev2 + nums[i];
        prev2 = prev1;
        prev1 = current;
    }
    
    return current;
}

int main() {
    int nums[] = {2, 7, 9, 3, 1};
    int result = rob(nums, sizeof(nums)/sizeof(nums[0]));
    printf("Max amount that can be robbed: %d\n", result);
    return 0;
}
using System;
class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        
        int prev1 = 0, prev2 = 0, current = 0;
        
        foreach (var num in nums) {
            int temp = prev1;
            prev1 = Math.Max(prev2 + num, prev1);
            prev2 = temp;
        }
        return prev1;
    }

    static void Main() {
        int[] nums = {2, 7, 9, 3, 1};
        Solution sol = new Solution();
        Console.WriteLine("Max amount that can be robbed: " + sol.Rob(nums));
    }
}

The optimized space Python solution abandons the use of a dp list in favor of tracking the last two maximum results on each iteration, consistent with the choices made of rob or not considering the current house.

Complexity

Time Complexity: O(n) - Go through each house's potential once.
Space Complexity: O(1) - Reduced to constant storage using three integers.

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i), which represents the maximum amount of money that can be stolen starting from the i-th house. Thus, the answer is dfs(0).

The execution process of the function dfs(i) is as follows:

  • If i \ge len(nums), it means all houses have been considered, and we directly return 0;
  • Otherwise, consider stealing from the i-th house, then dfs(i) = nums[i] + dfs(i+2); if not stealing from the i-th house, then dfs(i) = dfs(i+1).
  • Return max(nums[i] + dfs(i+2), dfs(i+1)).

To avoid repeated calculations, we use memoization search. The result of dfs(i) is saved in an array or hash table. Before each calculation, we first check if it has been calculated. If so, we directly return the result.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.

function rob(nums: number[]): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i] < 0) {
            f[i] = Math.max(nums[i] + dfs(i + 2), dfs(i + 1));
        }
        return f[i];
    };
    return dfs(0);
}
func rob(nums []int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] < 0 {
			f[i] = max(nums[i]+dfs(i+2), dfs(i+1))
		}
		return f[i]
	}
	return dfs(0)
}
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        fn dfs(i: usize, nums: &Vec<i32>, f: &mut Vec<i32>) -> i32 {
            if i >= nums.len() {
                return 0;
            }
            if f[i] < 0 {
                f[i] = (nums[i] + dfs(i + 2, nums, f)).max(dfs(i + 1, nums, f));
            }
            f[i]
        }

        let n = nums.len();
        let mut f = vec![-1; n];
        dfs(0, &nums, &mut f)
    }
}
Try this approach in the editor

Approach 4: Dynamic Programming

We define f[i] as the maximum total amount that can be robbed from the first i houses, initially f[0]=0, f[1]=nums[0].

Consider the case where i \gt 1, the ith house has two options:

  • Do not rob the ith house, the total amount of robbery is f[i-1];
  • Rob the ith house, the total amount of robbery is f[i-2]+nums[i-1];

Therefore, we can get the state transition equation:

$ f[i]= \begin{cases} 0, & i=0 \ nums[0], & i=1 \ max(f[i-1],f[i-2]+nums[i-1]), & i \gt 1 \end{cases}

The final answer is f[n], where n is the length of the array.

The time complexity is O(n), and the space complexity is O(n). Where n$ is the length of the array.

function rob(nums: number[]): number {
    const n = nums.length;
    const f: number[] = Array(n + 1).fill(0);
    f[1] = nums[0];
    for (let i = 2; i <= n; ++i) {
        f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
    }
    return f[n];
}
func rob(nums []int) int {
	n := len(nums)
	f := make([]int, n+1)
	f[1] = nums[0]
	for i := 2; i <= n; i++ {
		f[i] = max(f[i-1], f[i-2]+nums[i-1])
	}
	return f[n]
}
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut f = vec![0; n + 1];
        f[1] = nums[0];
        for i in 2..=n {
            f[i] = f[i - 1].max(f[i - 2] + nums[i - 1]);
        }
        f[n]
    }
}
Try this approach in the editor

Approach 5: Dynamic Programming (Space Optimization)

We notice that when i \gt 2, f[i] is only related to f[i-1] and f[i-2]. Therefore, we can use two variables instead of an array to reduce the space complexity to O(1).

function rob(nums: number[]): number {
    let [f, g] = [0, 0];
    for (const x of nums) {
        [f, g] = [Math.max(f, g), f + x];
    }
    return Math.max(f, g);
}
func rob(nums []int) int {
	f, g := 0, 0
	for _, x := range nums {
		f, g = max(f, g), f+x
	}
	return max(f, g)
}
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let mut f = [0, 0];
        for x in nums {
            f = [f[0].max(f[1]), f[0] + x];
        }
        f[0].max(f[1])
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming - Iterative Approach

Time Complexity: O(n) - The full list is iterated through.
Space Complexity: O(n) - Using a list to keep track of current states.

Dynamic Programming - Optimized Space Approach

Time Complexity: O(n) - Go through each house's potential once.
Space Complexity: O(1) - Reduced to constant storage using three integers.

Memoization Search–
Dynamic Programming–
Dynamic Programming (Space Optimization)–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming - Iterative DP ArrayO(n)O(n)Best for understanding the DP recurrence and explaining the transition clearly in interviews
Dynamic Programming - Optimized SpaceO(n)O(1)Preferred in production or interviews when memory optimization is expected

Frequently asked questions

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.

Comments

Next problem · similarMaximum Product SubarrayMedium
Now write it yourselfClose this page and solve House Robber in the editor, without looking.
Practise House Robber