#101 Medium Time O(n) Space O(1) Animated

House Robber

Maximize robbery money without robbing adjacent houses.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Dynamic programming: reuse smaller answers

Define one state whose value fully solves a smaller version of the problem.

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Define one state whose value fully solves a smaller version of the problem.

Common Pitfall

Write the recurrence in words before optimizing the storage.

Description

Maximize robbery money without robbing adjacent houses.

Constraints

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

Solution — Dynamic Programming (1D)

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Define the state precisely.
Set base cases.
Fill states in dependency order.
Return the final state.

def rob(nums):
    rob1, rob2 = 0, 0
    
    # [rob1, rob2, n, n+1, ...]
    for n in nums:
        temp = max(n + rob1, rob2)
        rob1 = rob2
        rob2 = temp
    return rob2

Min Cost Climbing Stairs

House Robber II

House Robber

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)