198. House Robber (Medium)

Problem

Given nums[i] = money at house i, return the maximum amount you can rob without robbing two adjacent houses.

Example

nums = [1, 2, 3, 1] → 4 (rob houses 0 and 2)
nums = [2, 7, 9, 3, 1] → 12 (rob 0, 2, 4)

LeetCode 198 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive with take/skip

f(i) = max(nums[i] + f(i+2), f(i+1)).

def rob(nums):
    def f(i):                              # L1: define recursive helper
        if i >= len(nums):                 # L2: O(1) base case check
            return 0
        return max(nums[i] + f(i + 2), f(i + 1))  # L3: two recursive calls each time
    return f(0)                            # L4: O(1) entry call

function rob(nums: number[]): number {
    function f(i: number): number {                                    // L1: define helper
        if (i >= nums.length) return 0;                               // L2: O(1) base case
        return Math.max(nums[i] + f(i + 2), f(i + 1));               // L3: two recursive calls
    }
    return f(0);                                                       // L4: O(1) entry call
}

final class Solution {
    func rob(_ nums: [Int]) -> Int { func solve(_ i: Int) -> Int { i >= nums.count ? 0 : max(solve(i + 1), nums[i] + solve(i + 2)) }; return solve(0) }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (base case)	$O(1)$	$O(2ⁿ)$ unique + repeated calls	$O(2ⁿ)$
L3 (two recursive branches)	$O(1)$ + subtree cost	$O(2ⁿ)$ calls	$O(2ⁿ)$ ← dominates
L4 (entry)	$O(1)$	1	$O(1)$

Every call fans out into two subproblems with no memoization, so the call tree is a full binary tree of depth n. Total nodes: $O(2ⁿ)$ .

Complexity

Time: $O(2ⁿ)$ , driven by L3 (unbounded branching without caching).
Space: $O(n)$ for the recursion stack at depth n.

Approach 2: Memoized

from functools import lru_cache

def rob(nums):
    n = len(nums)
    @lru_cache(maxsize=None)               # L1: O(1) decoration
    def f(i):
        if i >= n:                         # L2: O(1) base case check
            return 0
        return max(nums[i] + f(i + 2), f(i + 1))  # L3: O(1) per unique call (cache hits after)
    return f(0)                            # L4: O(1) entry call

function rob(nums: number[]): number {
    const n = nums.length;
    const memo = new Map<number, number>();
    function f(i: number): number {
        if (i >= n) return 0;                                         // L2: O(1) base case
        if (memo.has(i)) return memo.get(i)!;
        const result = Math.max(nums[i] + f(i + 2), f(i + 1));      // L3: O(1) per unique call
        memo.set(i, result);
        return result;
    }
    return f(0);                                                       // L4: O(1) entry call
}

final class Solution {
    func rob(_ nums: [Int]) -> Int { var memo: [Int: Int] = [:]; func solve(_ i: Int) -> Int { if i >= nums.count { return 0 }; if let v = memo[i] { return v }; let v = max(solve(i + 1), nums[i] + solve(i + 2)); memo[i] = v; return v }; return solve(0) }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (lru_cache setup)	$O(1)$	1	$O(1)$
L2 (base case)	$O(1)$	n+1 unique calls	$O(n)$
L3 (compute + cache store)	$O(1)$	n unique calls	$O(n)$ ← dominates
L4 (entry)	$O(1)$	1	$O(1)$

Each index i is computed exactly once; subsequent calls return a cached result in $O(1)$ . The n subproblems each do $O(1)$ work, giving $O(n)$ total.

Complexity

Time: $O(n)$ , driven by L3 (n unique subproblems, each computed once).
Space: $O(n)$ for the cache and recursion stack.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Bottom-up DP array

dp[i] = max money robbing houses 0..i. dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Two valid meanings for the DP index

An index can identify a house or count how many houses have been considered. Both conventions work, but their allocation, base cases, and recurrence must agree:

Detail	House-index state	Prefix-length state
Meaning of `dp[i]`	Best money from houses `0` through `i`	Best money from the first `i` houses
Current house	`nums[i]`	`nums[i - 1]`
Table length	`n`	`n + 1`
Base cases	`dp[0] = nums[0]`, then best of the first two	`dp[0] = 0`, `dp[1] = nums[0]`
Loop	`range(2, n)`	`range(2, n + 1)`
Final answer	`dp[n - 1]`	`dp[n]`

The implementation below uses house indices. The prefix-length DP convention is often easier to reason about because it gives the empty input prefix its own slot.

Walkthrough: count houses, then choose take or skip

With the prefix-length convention, dp[i] means the best total from the first i houses, whether or not the last of those houses is robbed.

At i = 3 for [2, 7, 9, 3, 1], the current house is nums[2] = 9. There are two possibilities:

Skip it: Keep dp[2] = 7, the best result from the first two houses.
Rob it: Add 9 to dp[1] = 2. The neighboring house containing 7 is excluded, so the total is 11.

Take max(7, 11). We are choosing the better legal plan, not adding the two plans together.

Input index:         0   1   2   3   4
nums:               [2,  7,  9,  3,  1]

Houses considered:   0   1   2   3   4   5
Current value:       -   2   7   9   3   1
dp:                 [0,  2,  7, 11, 11, 12]

Houses `i`	Current house	Skip: `dp[i - 1]`	Rob: `dp[i - 2] + nums[i - 1]`	`dp[i]`
2	`nums[1] = 7`	`2`	`0 + 7 = 7`	`7`
3	`nums[2] = 9`	`7`	`2 + 9 = 11`	`11`
4	`nums[3] = 3`	`11`	`7 + 3 = 10`	`11`
5	`nums[4] = 1`	`11`	`11 + 1 = 12`	`12`

Here is that version in Python:

def rob_prefix(nums: list[int]) -> int:
    n = len(nums)
    if not nums:
        return 0
    dp = [0] * (n + 1)                         # O(n) allocation
    dp[1] = nums[0]                            # O(1) base case
    for i in range(2, n + 1):                  # n - 1 iterations
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
    return dp[n]                              # O(1) lookup

Each loop iteration performs a fixed number of lookups, an addition, and a comparison, all $O(1)$ . Allocation plus the loop gives $O(n)$ time and $O(n)$ extra space. For a single house, the loop is empty and the initialized dp[1] is already the answer. The empty-input guard is optional robustness beyond the problem’s nonempty-input constraint.

Common mistakes: mixing counts with positions

If dp[1] = nums[0], the state is counting houses. Allocating only n slots and then writing dp[n] goes beyond the table. Reading nums[i] at that same step also goes beyond the input: the ith house is at index i - 1.

Starting the recurrence at 0 creates a different problem: dp[i - 1] and dp[i - 2] become negative indices in Python. Those read from the end of the list rather than representing smaller solved prefixes, or raise an error when the list is too short. Fill the base cases first and start at 2.

The constraint is adjacency, not index parity. Choosing all even-indexed houses or all odd-indexed houses is insufficient. For [2, 1, 1, 2], either fixed parity totals 3, while taking indices 0 and 3 gives 4.

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    dp = [0] * n                              # L1: O(n) allocation
    dp[0] = nums[0]                           # L2: base case
    dp[1] = max(nums[0], nums[1])             # L3: base case
    for i in range(2, n):                     # L4: loop n-2 times
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])  # L5: O(1) recurrence
    return dp[n-1]                            # L6: O(1) return

function rob(nums: number[]): number {
    const n = nums.length;
    if (n === 1) return nums[0];
    const dp = new Array(n).fill(0);              // L1: O(n) allocation
    dp[0] = nums[0];                              // L2: base case
    dp[1] = Math.max(nums[0], nums[1]);           // L3: base case
    for (let i = 2; i < n; i++) {                // L4: loop n-2 times
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);  // L5: O(1) recurrence
    }
    return dp[n - 1];                            // L6: O(1) return
}

final class Solution {
    func rob(_ nums: [Int]) -> Int { if nums.count == 1 { return nums[0] }; var dp = Array(repeating: 0, count: nums.count + 1); dp[1] = nums[0]; for i in 2...nums.count { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) }; return dp[nums.count] }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (allocate dp)	$O(n)$	1	$O(n)$
L2, L3 (base cases)	$O(1)$	1 each	$O(1)$
L4, L5 (loop + recurrence)	$O(1)$	n - 2	$O(n)$ ← dominates
L6 (return)	$O(1)$	1	$O(1)$

Complexity

Time: $O(n)$ , driven by L4/L5 (n - 2 iterations).
Space: $O(n)$ for the dp array.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 4: Bottom-up with two variables (optimal)

prev2 = dp[i-2], prev1 = dp[i-1]. dp[i] = max(prev1, prev2 + nums[i]).

Before processing a house, prev1 is the best total from all earlier houses, and prev2 is the best total from the prefix ending before its immediate neighbor. Use both old values to compute the next result, then shift them forward. Python’s simultaneous assignment evaluates the right-hand expressions before changing either variable. Updating prev2 first in separate statements would lose the older value needed for the rob choice.

Like Climbing Stairs, the table only needs its previous two results. The dependency shape permits the same space reduction, but the recurrence has a different purpose: stairs adds counts from distinct final moves, while House Robber maximizes the value of take/skip choices. Similar-looking dependencies do not imply the same base cases or combining operation.

def rob(nums):
    prev2, prev1 = 0, 0                    # L1: O(1) initialization
    for x in nums:                         # L2: loop over n elements
        prev2, prev1 = prev1, max(prev1, prev2 + x)  # L3: O(1) per iteration
    return prev1                           # L4: O(1) return

function rob(nums: number[]): number {
    let prev2 = 0, prev1 = 0;             // L1: O(1) initialization
    for (const x of nums) {               // L2: loop over n elements
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];  // L3: O(1) per iteration
    }
    return prev1;                         // L4: O(1) return
}

final class Solution {
    func rob(_ nums: [Int]) -> Int { var previous = 0, current = 0; for value in nums { (previous, current) = (current, max(current, previous + value)) }; return current }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init vars)	$O(1)$	1	$O(1)$
L2 (loop header)	$O(1)$	n+1 (including exit test)	$O(n)$
L3 (update vars)	$O(1)$	n	$O(n)$ ← dominates
L4 (return)	$O(1)$	1	$O(1)$

The entire DP table is collapsed to two scalars. Each step only needs the previous two values, so we discard everything else. No array allocation, no recursion overhead.

Complexity

Time: $O(n)$ , driven by L3 (single pass over nums).
Space: $O(1)$ , only two scalar variables regardless of input size.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Naive take/skip	$O(2ⁿ)$	$O(n)$
Memoized	$O(n)$	$O(n)$
Bottom-up, dp array	$O(n)$	$O(n)$
Bottom-up, two vars	$O(n)$	$O(1)$

This is the canonical “take or skip” DP pattern. Reappears in Paint House, Delete and Earn, and Best Time to Buy/Sell with Cooldown.

# Quick smoke tests, paste into a REPL or save as test_198_house_robber.py and run.
# Uses the canonical implementation (Approach 4: bottom-up two variables).

def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

def _run_tests():
    assert rob([1, 2, 3, 1]) == 4        # LeetCode example 1: rob houses 0 and 2
    assert rob([2, 7, 9, 3, 1]) == 12    # LeetCode example 2: rob houses 0, 2, 4
    assert rob([0]) == 0                  # single house with zero value
    assert rob([5]) == 5                  # single house
    assert rob([2, 1]) == 2              # two houses, take the larger
    assert rob([1, 3, 1, 3, 100]) == 103 # skip to last big value
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function rob(nums: number[]): number {
    let prev2 = 0, prev1 = 0;
    for (const x of nums) {
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];
    }
    return prev1;
}

console.assert(rob([1, 2, 3, 1]) === 4);
console.assert(rob([2, 7, 9, 3, 1]) === 12);
console.assert(rob([0]) === 0);
console.assert(rob([5]) === 5);
console.assert(rob([2, 1]) === 2);
console.assert(rob([1, 3, 1, 3, 100]) === 103);
console.log('all tests pass');

Arrays, input; collapsed DP

Dynamic Programming, state-and-transition tactics for solving overlapping subproblems with cached answers.
Tabulation: prefix-length DP, distinguish a count of considered houses from the current house’s zero-based index.
State Compression, DP memory tactics for keeping only the previous states needed for the next transition.

198. House Robber (Medium)

Problem

Try it yourself

Approach 1: Recursive with take/skip

Approach 2: Memoized

Approach 3: Bottom-up DP array

Two valid meanings for the DP index

Walkthrough: count houses, then choose take or skip

Common mistakes: mixing counts with positions

Approach 4: Bottom-up with two variables (optimal)

Summary

Test cases

Related data structures

Related concepts