Sign in
Skip to solution
mediumDSA

How do you solve the house robber problem?

494 views
01

Understand the problem

Explain non-adjacent max sum.

dp
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

You can't rob two adjacent houses, so dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Track just two running variables for O(n) time, O(1) space. The circular variant runs it twice, excluding the first or last house.

Solution ready — 2 min read

Classified // press E to declassify

04

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

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 69 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track