Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

House Robber

House Robber explained: the take-or-skip DP for the maximum sum of non-adjacent elements, O(n) time and O(1) space, tested Python and a live DP visual.

Also searched as: house robber dp · maximum sum of non-adjacent elements · max sum no two adjacent

🪙

Try it live Free

Coin Change (DP)

The Coin Change lab shows the same idea in a 1D table: watch dp[] fill left to right, each cell built from earlier answers, which is exactly how best(i) is built from best(i-1) and best(i-2).

Also useful: Recursion & the Call Stack

Open the playground →

The problem

A row of houses each holds some amount of money (non-negative integers). You may take money from any houses you like, but never from two neighbouring houses. Return the largest total you can collect.

Input[2, 7, 9, 3, 1]
Output12

Take 2 + 9 + 1.

Input[2, 1, 1, 2]
Output4

Take the first and last house.

The key insight

At each house you make one decision: take it (then you add its money to the best total from two houses back) or skip it (then you keep the best total up to the previous house). The best answer up to house i is the larger of those two, and it depends only on the previous two answers.

Brute force first: Trying every subset of non-adjacent houses is exponential, roughly O(1.6n).

Step-by-step approach

  1. Let best(i) be the most money from houses 0..i.
  2. Recurrence: best(i) = max(best(i-1), best(i-2) + nums[i]).
  3. Start with prev2 = 0 and prev1 = 0 (no houses yet).
  4. For each house, compute the new best and shift the two variables forward.
  5. Return prev1 after the last house.

Python solution

PYTHON 3tested
def rob(nums):
    prev2, prev1 = 0, 0          # best up to i-2, best up to i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Complexity

TimeO(n)
SpaceO(1)

One pass over the houses with constant work each, and only two running values are kept.

Common mistakes

Frequently asked questions

What is the time and space complexity of House Robber?

O(n) time with a single pass, and O(1) space because each answer only needs the previous two.

How do I solve House Robber when the houses are in a circle?

The first and last houses become neighbours. Run the linear solution twice, once on houses 0..n-2 and once on 1..n-1, and return the larger result (with a special case for a single house).

How do I recover which houses were robbed?

Keep the full dp array, then walk backwards: if dp[i] equals dp[i-1], house i was skipped; otherwise it was taken and you jump to i-2.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.