mediumDSA

How do you solve the house robber problem?

Q: How do you solve the house robber problem?

**Intuition.** At each house you choose: **rob it** (and add the best from two houses back, since adjacent houses can't both be robbed) or **skip it** (keep the best so far). So best[i] = max(best[i-1], best[i-2] + nums[i]) — and you only ever need the last two results, giving O(1) space. rob i + best two-back, or skip i → can't rob adjacent 2 <rect x="130" y="55" width="50" height="40" rx="6" fill="currentColor" fil

494 views

Understand the problem

Explain non-adjacent max sum.

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Rolling two-variable DP

Run Playground

def rob(nums):
    prev, curr = 0, 0    # best up to i-2, best up to i-1
    for x in nums:
        prev, curr = curr, max(curr, prev + x)
    return curr


# --- demo ---
print(rob([2, 7, 9, 3, 1]))   # 12  (2 + 9 + 1)
print(rob([1, 2, 3, 1]))      # 4   (1 + 3)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the maximum product subarray?

How do you solve the word break problem?