House Robber — Solution in C++, Java, Python, Go

Given an integer array nums representing the amount of money at each house along a street, return the maximum amount you can rob tonight without robbing two adjacent houses. Adjacent houses have connected security systems that will alert the police if both are broken into on the same night.

Examples

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and house 3 (money = 3). Total = 1 + 3 = 4.

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1). Total = 2 + 9 + 1 = 12.

Constraints

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

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

At each house we have two choices: rob it (and skip the next house) or skip it (and move to the next house). This creates a binary decision tree. The recurrence is rob(i) = max(nums[i] + rob(i+2), rob(i+1)). Without memoization, many subproblems are recomputed, resulting in exponential time.

Algorithm

Define a recursive function starting at index `0`.
Base case: if index `>= n`, return `0`.
Option 1: rob the current house and recurse from `index + 2`.
Option 2: skip the current house and recurse from `index + 1`.
Return the maximum of both options.

TimeO(2^n)SpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    int rob(vector<int>& nums) {
        return helper(nums, 0);
    }

    int helper(vector<int>& nums, int i) {
        if (i >= nums.size()) return 0;
        return max(nums[i] + helper(nums, i + 2), helper(nums, i + 1));
    }
};

Java 21

class Solution {
    public int rob(int[] nums) {
        return helper(nums, 0);
    }

    private int helper(int[] nums, int i) {
        if (i >= nums.length) return 0;
        return Math.max(nums[i] + helper(nums, i + 2), helper(nums, i + 1));
    }
}

Python 3.12

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def helper(i: int) -> int:
            if i >= len(nums):
                return 0
            return max(nums[i] + helper(i + 2), helper(i + 1))

        return helper(0)

Go 1.26

func rob(nums []int) int {
    var helper func(i int) int
    helper = func(i int) int {
        if i >= len(nums) {
            return 0
        }
        take := nums[i] + helper(i+2)
        skip := helper(i + 1)
        if take > skip {
            return take
        }
        return skip
    }
    return helper(0)
}

Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the maximum money obtainable from houses 0 through i. At each house, the best we can do is either rob it (adding to the best from two houses back) or skip it (keeping the best from the previous house). The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Algorithm

Handle edge cases: if `n == 1`, return `nums[0]`.
Create array `dp` of size `n`. Set `dp[0] = nums[0]`, `dp[1] = max(nums[0], nums[1])`.
For each `i` from 2 to `n-1`, set `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`.
Return `dp[n-1]`.

TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17

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

Java 21

class Solution {
    public int rob(int[] nums) {
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

Python 3.12

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[n - 1]

Go 1.26

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = nums[0]
    if nums[1] > dp[1] {
        dp[1] = nums[1]
    }
    for i := 2; i < n; i++ {
        dp[i] = dp[i-1]
        if dp[i-2]+nums[i] > dp[i] {
            dp[i] = dp[i-2] + nums[i]
        }
    }
    return dp[n-1]
}

Approach 3

Space-Optimized DP

Intuition

Since each state only depends on the previous two values, we can track just two variables instead of a full array. We iterate through the houses, updating the running maximum without needing extra storage.

Algorithm

Initialize `prev2 = 0` and `prev1 = 0`.
For each house value, compute `current = max(prev1, prev2 + nums[i])`.
Shift: `prev2 = prev1`, `prev1 = current`.
Return `prev1`.

TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int curr = max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

Java 21

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int curr = Math.max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

Python 3.12

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0
        for num in nums:
            curr = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = curr
        return prev1

Go 1.26

func rob(nums []int) int {
    prev2, prev1 := 0, 0
    for _, num := range nums {
        curr := prev1
        if prev2+num > curr {
            curr = prev2 + num
        }
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

Frequently asked questions

What is the optimal time complexity of House Robber?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does House Robber use?

House Robber is a medium-level Dynamic Programming problem involving Array, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can House Robber be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...

Input

nums=

[1,2,3,1]

Expected Output