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

Python

▶ Run Python ↻ Reset

idle

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).

TypeScript

▶ Run TS ↻ Reset

idle

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).

Go

▶ Run Go ↻ Reset

idle

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)).

Python

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

TypeScript

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
}

Swift

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

Python

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

TypeScript

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
}

Swift

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:

Python

▶ Run Python ↻ Reset

idle

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

TypeScript

▶ Run TS ↻ Reset

idle

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

Go

▶ Run Go ↻ Reset

idle

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]).

Python

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

TypeScript

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
}

Swift

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:

Python

▶ Run Python ↻ Reset

idle

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

TypeScript

▶ Run TS ↻ Reset

idle

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

Go

▶ Run Go ↻ Reset

idle

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]).

Python

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

TypeScript

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
}

Swift

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:

Python

▶ Run Python ↻ Reset

idle

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

TypeScript

▶ Run TS ↻ Reset

idle

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

Go

▶ Run Go ↻ Reset

idle

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.

Test cases

Python

# 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()

TypeScript

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');

Related data structures

• Arrays, input; collapsed DP

Related concepts

• Dynamic Programming, state-and-transition tactics for solving overlapping subproblems with cached answers.
• State Compression, dP memory tactics for keeping only the previous states needed for the next transition.