House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Robbers have a constraint: you cannot rob two adjacent houses.

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob without robbing adjacent houses.

What to notice first

• You cannot rob two adjacent houses in a single robbery.
• You want to maximize the total amount of money stolen.
• Every house is independent: robbing one doesn’t affect the value of another, only the adjacency rule applies.
• This is a classic DP problem where each house presents a choice: rob or skip.

Examples

nums	Output	Explanation
[1, 2, 3, 1]	4	Rob house 0 (money = 1) and house 2 (money = 3). Total = 1 + 3 = 4
[2, 7, 9, 3, 1]	12	Rob house 1 (money = 7) and house 3 (money = 3). Total = 7 + 9 = 12
[5, 3, 4, 11, 2]	16	Rob houses 0, 2, 4. Total = 5 + 4 + 11 = 20… wait, that’s 20. Let me recalculate: houses 0 (5) + 2 (4) + 4 (2) = 11, or 0 (5) + 3 (11) = 16 ✓

Constraints

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

Real-World Applications

Where this pattern appears

• Financial portfolio optimization — selecting non-adjacent stocks to maximize returns while managing risk.
• Work scheduling — choosing non-consecutive shifts to maximize pay while respecting rest periods.
• Route planning — selecting non-adjacent waypoints in a city to maximize resources collected.
• Product bundle selection — choosing complementary (non-competing) products to maximize revenue.

Complexity Comparison

Approach	Time	Space	Description
DP Array	O(n)	O(n)	Store all intermediate results for clarity
Space-Optimized	O(n)	O(1)	Only track the last two values

Which approach should you learn first?

• Pick DP Array if you want clarity and ease of debugging.
• Pick Space-Optimized if you want to show optimization skills and understand the minimal state needed.

Best For Clarity

DP Array

O(n) time · O(n) space

Space Optimized

O(1) Variables

O(n) time · O(1) space

Approach 1: DP Array

★ Recommended

Create a DP array where dp[i] represents the maximum money you can rob from houses 0 to i.

For each house i, you have two choices:

• Rob house i: take nums[i] + dp[i-2] (the money from this house plus the max from non-adjacent houses before it)
• Skip house i: take dp[i-1] (the max from the house before it)

The recurrence is: dp[i] = max(nums[i] + dp[i-2], dp[i-1])

⏱ Time O(n) Single pass 💾 Space O(n) DP array storage

Step-by-step Example

Input: nums = [2, 7, 9, 3, 1]

i	nums[i]	Choice (Rob)	Choice (Skip)	dp[i]	Explanation
0	2	2	0	2	Rob house 0
1	7	7	2	7	Rob house 1 (better than house 0)
2	9	9 + 2 = 11	7	11	Rob house 2 and non-adjacent house 0
3	3	3 + 7 = 10	11	11	Skip house 3, keep previous max
4	1	1 + 11 = 12	11	12	Rob house 4 with best from 0-2

Result: Max money = 12 (houses 1 and 3, or houses 0 and 2)

Animated walkthrough

How the DP solution maximizes stolen money

Use Next or Autoplay to watch the maximum money grow as we evaluate each house's rob vs skip decision.

Back Autoplay Next Reset

Step 1 of 5 Target: 12

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function houseRobberDpArray(nums):
    if nums is empty:
        return 0
    if nums length is 1:
        return nums[0]

    dp = array of size len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i from 2 to len(nums) - 1:
        dp[i] = max(nums[i] + dp[i-2], dp[i-1])

    return dp[len(nums) - 1]

Solution Code

Python

house_robber_dp_array.py

from typing import List


def house_robber_dp_array(nums: List[int]) -> int:
    """
    Rob houses with maximum money using DP array approach.

    Time Complexity: O(n)
    Space Complexity: O(n)

    dp[i] = maximum money robbing houses 0 to i
    For each house i, we choose the max of:
    - Rob house i + dp[i-2] (skip i-1)
    - Don't rob house i + dp[i-1] (keep i-1)
    """
    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(nums[i] + dp[i - 2], dp[i - 1])

    return dp[-1]


if __name__ == "__main__":
    print(house_robber_dp_array([1, 2, 3, 1]))      # 4 (rob house 0 and 2)
    print(house_robber_dp_array([2, 7, 9, 3, 1]))   # 12 (rob houses 1 and 3)
    print(house_robber_dp_array([5, 3, 4, 11, 2]))  # 16 (rob houses 0, 2, 4)

C++

house_robber_dp_array.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Rob houses with maximum money using DP array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
int houseRobberDpArray(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    vector<int> dp(nums.size());
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < nums.size(); i++) {
        dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
    }

    return dp.back();
}

int main() {
    vector<int> test1 = {1, 2, 3, 1};
    cout << houseRobberDpArray(test1) << endl;  // 4

    vector<int> test2 = {2, 7, 9, 3, 1};
    cout << houseRobberDpArray(test2) << endl;  // 12

    return 0;
}

Java

HouseRobberDpArray.java

/**
 * Rob houses with maximum money using DP array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
public class HouseRobberDpArray {
    public static int houseRobberDpArray(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(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(houseRobberDpArray(new int[]{1, 2, 3, 1}));      // 4
        System.out.println(houseRobberDpArray(new int[]{2, 7, 9, 3, 1}));   // 12
    }
}

JavaScript

house_robber_dp_array.js

/**
 * Rob houses with maximum money using DP array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function houseRobberDpArray(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    const dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }

    return dp[nums.length - 1];
}

console.log(houseRobberDpArray([1, 2, 3, 1]));      // 4
console.log(houseRobberDpArray([2, 7, 9, 3, 1]));   // 12

Rust

house_robber_dp_array.rs

/**
 * Rob houses with maximum money using DP array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
pub fn house_robber_dp_array(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    if nums.len() == 1 {
        return nums[0];
    }

    let mut dp = vec![0; nums.len()];
    dp[0] = nums[0];
    dp[1] = nums[0].max(nums[1]);

    for i in 2..nums.len() {
        dp[i] = (nums[i] + dp[i - 2]).max(dp[i - 1]);
    }

    dp[nums.len() - 1]
}

fn main() {
    println!("{}", house_robber_dp_array(vec![1, 2, 3, 1]));      // 4
    println!("{}", house_robber_dp_array(vec![2, 7, 9, 3, 1]));   // 12
}

Go

house_robber_dp_array.go

package main

import "fmt"

/*
 * Rob houses with maximum money using DP array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
func houseRobberDpArray(nums []int) int {
  if len(nums) == 0 {
    return 0
  }
  if len(nums) == 1 {
    return nums[0]
  }

  dp := make([]int, len(nums))
  dp[0] = nums[0]
  if nums[1] > nums[0] {
    dp[1] = nums[1]
  } else {
    dp[1] = nums[0]
  }

  for i := 2; i < len(nums); i++ {
    rob := nums[i] + dp[i-2]
    skip := dp[i-1]
    if rob > skip {
      dp[i] = rob
    } else {
      dp[i] = skip
    }
  }

  return dp[len(nums)-1]
}

func main() {
  fmt.Println(houseRobberDpArray([]int{1, 2, 3, 1}))      // 4
  fmt.Println(houseRobberDpArray([]int{2, 7, 9, 3, 1}))   // 12
}

Approach 2: Space-Optimized

🎯 Interview Favourite

Instead of storing the entire DP array, observe that dp[i] only depends on dp[i-1] and dp[i-2]. Therefore, we only need two variables: prev1 (max money up to house i-1) and prev2 (max money up to house i-2).

This approach reduces space complexity from O(n) to O(1) while maintaining the same time complexity.

⏱ Time O(n) Single pass 💾 Space O(1) Only two variables

Step-by-step Example

Input: nums = [2, 7, 9, 3, 1]

i	nums[i]	prev2	prev1	current	Update
Start	—	2	7	—	Initialize with first two houses
2	9	2	7	11	max(9+2, 7) = 11, shift: prev2=7, prev1=11
3	3	7	11	11	max(3+7, 11) = 11, shift: prev2=11, prev1=11
4	1	11	11	12	max(1+11, 11) = 12

Result: Max money = 12

Pseudocode

function houseRobberSpaceOptimized(nums):
    if nums is empty:
        return 0
    if nums length is 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i from 2 to len(nums) - 1:
        current = max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = current

    return prev1

Solution Code

Python

house_robber_space_optimized.py

from typing import List


def house_robber_space_optimized(nums: List[int]) -> int:
    """
    Rob houses with maximum money using space-optimized approach.

    Time Complexity: O(n)
    Space Complexity: O(1)

    We only need the previous two values: prev2 (dp[i-2]) and prev1 (dp[i-1])
    To rob house i optimally, we track:
    - prev2: max money up to house i-2
    - prev1: max money up to house i-1
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]          # dp[0]
    prev1 = max(nums[0], nums[1])  # dp[1]

    for i in range(2, len(nums)):
        current = max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = current

    return prev1


if __name__ == "__main__":
    print(house_robber_space_optimized([1, 2, 3, 1]))      # 4
    print(house_robber_space_optimized([2, 7, 9, 3, 1]))   # 12
    print(house_robber_space_optimized([5, 3, 4, 11, 2]))  # 16

C++

house_robber_space_optimized.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
int houseRobberSpaceOptimized(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);

    for (int i = 2; i < nums.size(); i++) {
        int current = max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

int main() {
    vector<int> test1 = {1, 2, 3, 1};
    cout << houseRobberSpaceOptimized(test1) << endl;  // 4

    vector<int> test2 = {2, 7, 9, 3, 1};
    cout << houseRobberSpaceOptimized(test2) << endl;  // 12

    return 0;
}

Java

HouseRobberSpaceOptimized.java

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class HouseRobberSpaceOptimized {
    public static int houseRobberSpaceOptimized(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(houseRobberSpaceOptimized(new int[]{1, 2, 3, 1}));      // 4
        System.out.println(houseRobberSpaceOptimized(new int[]{2, 7, 9, 3, 1}));   // 12
    }
}

JavaScript

house_robber_space_optimized.js

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function houseRobberSpaceOptimized(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev2 = nums[0];
    let prev1 = Math.max(nums[0], nums[1]);

    for (let i = 2; i < nums.length; i++) {
        const current = Math.max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

console.log(houseRobberSpaceOptimized([1, 2, 3, 1]));      // 4
console.log(houseRobberSpaceOptimized([2, 7, 9, 3, 1]));   // 12

Rust

house_robber_space_optimized.rs

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
pub fn house_robber_space_optimized(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    if nums.len() == 1 {
        return nums[0];
    }

    let mut prev2 = nums[0];
    let mut prev1 = nums[0].max(nums[1]);

    for i in 2..nums.len() {
        let current = (nums[i] + prev2).max(prev1);
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

fn main() {
    println!("{}", house_robber_space_optimized(vec![1, 2, 3, 1]));      // 4
    println!("{}", house_robber_space_optimized(vec![2, 7, 9, 3, 1]));   // 12
}

Go

house_robber_space_optimized.go

package main

import "fmt"

/*
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
func houseRobberSpaceOptimized(nums []int) int {
  if len(nums) == 0 {
    return 0
  }
  if len(nums) == 1 {
    return nums[0]
  }

  prev2 := nums[0]
  prev1 := nums[0]
  if nums[1] > nums[0] {
    prev1 = nums[1]
  }

  for i := 2; i < len(nums); i++ {
    rob := nums[i] + prev2
    skip := prev1
    var current int
    if rob > skip {
      current = rob
    } else {
      current = skip
    }
    prev2 = prev1
    prev1 = current
  }

  return prev1
}

func main() {
  fmt.Println(houseRobberSpaceOptimized([]int{1, 2, 3, 1}))      // 4
  fmt.Println(houseRobberSpaceOptimized([]int{2, 7, 9, 3, 1}))   // 12
}

Common mistakes

Watch for these pitfalls

• Forgetting the adjacency constraint: ensure you skip the house immediately before the one you rob.
• Base case errors: dp[1] should be the max of the first two houses, not just nums[1].
• Variable update order: in the space-optimized approach, update prev2 before prev1, or use a temporary variable.
• Off-by-one errors: the loop should iterate from index 2 to len(nums) - 1 (inclusive).
• Empty or single-house arrays: handle edge cases where nums.length <= 1.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

house_robber_space_optimized.py

from typing import List


def house_robber_space_optimized(nums: List[int]) -> int:
    """
    Rob houses with maximum money using space-optimized approach.

    Time Complexity: O(n)
    Space Complexity: O(1)

    We only need the previous two values: prev2 (dp[i-2]) and prev1 (dp[i-1])
    To rob house i optimally, we track:
    - prev2: max money up to house i-2
    - prev1: max money up to house i-1
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]          # dp[0]
    prev1 = max(nums[0], nums[1])  # dp[1]

    for i in range(2, len(nums)):
        current = max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = current

    return prev1


if __name__ == "__main__":
    print(house_robber_space_optimized([1, 2, 3, 1]))      # 4
    print(house_robber_space_optimized([2, 7, 9, 3, 1]))   # 12
    print(house_robber_space_optimized([5, 3, 4, 11, 2]))  # 16

C++

house_robber_space_optimized.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
int houseRobberSpaceOptimized(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);

    for (int i = 2; i < nums.size(); i++) {
        int current = max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

int main() {
    vector<int> test1 = {1, 2, 3, 1};
    cout << houseRobberSpaceOptimized(test1) << endl;  // 4

    vector<int> test2 = {2, 7, 9, 3, 1};
    cout << houseRobberSpaceOptimized(test2) << endl;  // 12

    return 0;
}

Java

HouseRobberSpaceOptimized.java

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class HouseRobberSpaceOptimized {
    public static int houseRobberSpaceOptimized(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(houseRobberSpaceOptimized(new int[]{1, 2, 3, 1}));      // 4
        System.out.println(houseRobberSpaceOptimized(new int[]{2, 7, 9, 3, 1}));   // 12
    }
}

JavaScript

house_robber_space_optimized.js

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function houseRobberSpaceOptimized(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev2 = nums[0];
    let prev1 = Math.max(nums[0], nums[1]);

    for (let i = 2; i < nums.length; i++) {
        const current = Math.max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

console.log(houseRobberSpaceOptimized([1, 2, 3, 1]));      // 4
console.log(houseRobberSpaceOptimized([2, 7, 9, 3, 1]));   // 12

Rust

house_robber_space_optimized.rs

/**
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
pub fn house_robber_space_optimized(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    if nums.len() == 1 {
        return nums[0];
    }

    let mut prev2 = nums[0];
    let mut prev1 = nums[0].max(nums[1]);

    for i in 2..nums.len() {
        let current = (nums[i] + prev2).max(prev1);
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

fn main() {
    println!("{}", house_robber_space_optimized(vec![1, 2, 3, 1]));      // 4
    println!("{}", house_robber_space_optimized(vec![2, 7, 9, 3, 1]));   // 12
}

Go

house_robber_space_optimized.go

package main

import "fmt"

/*
 * Rob houses with maximum money using space-optimized approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
func houseRobberSpaceOptimized(nums []int) int {
  if len(nums) == 0 {
    return 0
  }
  if len(nums) == 1 {
    return nums[0]
  }

  prev2 := nums[0]
  prev1 := nums[0]
  if nums[1] > nums[0] {
    prev1 = nums[1]
  }

  for i := 2; i < len(nums); i++ {
    rob := nums[i] + prev2
    skip := prev1
    var current int
    if rob > skip {
      current = rob
    } else {
      current = skip
    }
    prev2 = prev1
    prev1 = current
  }

  return prev1
}

func main() {
  fmt.Println(houseRobberSpaceOptimized([]int{1, 2, 3, 1}))      // 4
  fmt.Println(houseRobberSpaceOptimized([]int{2, 7, 9, 3, 1}))   // 12
}

Related Problems

• House Robber II ↗ Medium #213
• House Robber III ↗ Medium #337
• Delete and Earn ↗ Medium #740
• Climbing Stairs ↗ Easy #70

Interview Tips

Key trade-offs to discuss

• Why DP over brute force? Brute force checks all 2^n subsets. DP uses the optimal substructure to reduce to O(n).
• State representation: clearly explain what dp[i] represents and why only the last two values matter.
• Follow-up: House Robber II (circular): the same DP logic applies, but you handle the circular constraint by running two DP passes (excluding the first or last house).
• Edge cases: mention handling nums with 0 or 1 elements.
• Proof of correctness: the greedy property holds: at each house, the optimal choice is always to pick the maximum of robbing or skipping.

← Previous
#197 Rising Temperature Next
#199 Binary Tree Right Side View →