House robber explained: the dynamic programming solution

In this article

1. Before you start
2. Why interviewers ask this
3. House robber from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview questions learning path, which also covers patterns such as sliding window and sorting and sweeping.

Why interviewers ask this

House Robber is a standard practice problem, listed as LeetCode 198 and explained in NeetCode's solution write-up. A question like it separates candidates who guess a pattern from candidates who can reason about a choice at each step. It is the usual entry point to one-dimensional dynamic programming, and NeetCode's page on the circular variant names that topic as the prerequisite.

A weak answer reaches for "take the biggest values" or "take every other house" and cannot defend it. A strong answer states the choice at one house, writes the recurrence, and explains why storing results turns an exponential search into linear work. A Staff-level answer also reduces the memory to two variables and handles the circular and tree variants without starting over.

House robber from first principles

House Robber problem

The House Robber problem is a puzzle in which you receive an array of non-negative house values, may not take two houses that sit next to each other, and must return the largest total you can take.

Recurrence relation

A recurrence relation is a rule that gives the answer for one position in terms of the answers for earlier positions, so the whole problem is built from small, already solved pieces.

Memoization

Memoization is the practice of storing the result of a function call the first time it is computed, so a later call with the same input reads the stored result instead of repeating the work.

In plain words

Imagine a row of days, each paying a different amount, where you may not work two days in a row. For each day you ask one question. Is working today worth losing tomorrow? The analogy breaks here: you see every house's value before you start, while a real calendar does not show future pay.

In one precise sentence, the answer for houses 0 to i is the larger of two numbers. One is the answer for houses 0 to i minus one. The other is the value of house i plus the answer for houses 0 to i minus two. Dynamic programming is a method that solves a problem by solving its smaller subproblems once and combining them. A subproblem is the same question asked about a shorter row of houses.

Step 1: At each house the choice is rob or skip

The choice at one house has exactly two outcomes, and every solution is built from them. According to NeetCode's problem statement, the input is an array nums where nums[i] is the amount of money the house at position i holds, and you return the maximum amount you can rob without alerting the police. NeetCode's copy of the problem allows between 1 and 100 houses, as of October 2026.

Standing at house i, you either rob it or skip it. Robbing gives its value plus the best you can do starting two houses later, because the next house is now off limits. Skipping gives the best you can do starting at the next house. NeetCode's solution write-up frames the same two options: skip the house and go to i + 1, or rob it, take nums[i] and go to i + 2. As a recursive function dfs, the answer is the larger of nums[i] + dfs(i + 2) and dfs(i + 1). You now know the whole idea; the next steps make it fast.

Step 2: Plain recursion repeats the same work

Plain recursion tries both choices at every index and returns the better result, as NeetCode's solution notes describe, but it recomputes the same subproblems many times. Starting at house 0, the path "skip, then rob" and the path "rob" both arrive at house 2, and each recomputes everything after it.

AlgoMap's explanation says this leads to an exponential number of recursive calls. The number of calls grows by a factor near 1.6 for every house you add, a figure computed from the call counts shown in the worked example.¹

Memoization fixes it. Memoization stores the answer for each index the first time it is computed, so each index is solved once, which NeetCode and DesignGurus both describe, and the time falls to linear in the number of houses. If the index goes out of bounds, the function returns 0, since no houses remain.

Step 3: The recurrence keeps the better of skipping and robbing

The bottom-up form of the recurrence fills a table from left to right. Let best[i] be the largest total available from houses 0 to i. The table starts with best[0] = nums[0] and best[1] = max(nums[0], nums[1]), which are the cases with no earlier houses to look back at. Both AlgoMap and NeetCode give it as the larger of best[i-1] and nums[i] + best[i-2]:

best[i] = max(best[i-1], nums[i] + best[i-2])

The first term skips house i and keeps the best total so far. The second robs house i and adds its value to the best total from two houses back, which is the last total that cannot include house i minus one.

The common error is the flipped version, best[i] = max(best[i-1] + nums[i], best[i-2]). That version adds the current house's value even on the skip branch; on [2, 7, 9, 3, 1] it returns 20 instead of 12.¹ The mistake is subtle because the line looks almost identical, and the worked example below shows how the table goes wrong.

Step 4: Two variables replace the table

Each cell of the table depends only on the two cells before it, so the table is unnecessary. DesignGurus describes keeping the best total up to the current house and up to the previous house in two variables, which reuses the same recurrence and drops the extra space to a constant.

def rob(nums):
    prev2, prev1 = 0, 0   # best total two houses back, one house back
    for value in nums:
        prev2, prev1 = prev1, max(prev1, value + prev2)
    return prev1

Starting both variables at 0 also handles the first two houses without special cases. The loop does a fixed amount of work per house, so the time is linear and the space is constant. A common follow-up is this reduction, once the table version works.

1 · Rob or skip2 · Repeated work3 · Table4 · Two variablesReplay

Step-by-step description

1. Every house has two choices.
2. Plain recursion repeats subproblems.
3. Keep the better of skip and rob.
4. Only the last two totals matter.

• Each house is either robbed or skipped.
• Plain recursion repeats the same subproblems many times.
• The table keeps the larger of skipping a house and robbing it plus the best total two houses back.
• Two variables hold the last two totals, so extra space stays constant.

Each house is either robbed or skipped. Plain recursion repeats the same subproblems many times. The table keeps the larger of skipping a house and robbing it plus the best total two houses back. Two variables hold the last two totals, so extra space stays constant.

Worked example

Take the illustrative array [2, 7, 9, 3, 1] and fill the table one house at a time.¹ At each row the skip column is the previous best, the rob column is the house value plus the best from two houses back, and the best column is the larger of the two.

The best totals after each house are 2, 7, 11, 11 and 12. At house index 3 the best total stays at 11 because robbing is worse than skipping. Walking back from the end, the final total of 12 came from robbing house 4, which means the previous robbed house is two back at index 2, then index 0. That is 2 + 9 + 1 = 12.¹ A second check: the array [1, 2, 3, 1] has a best total of 4, from houses 0 and 2.¹

Text description of the diagram

• The best totals after each house are 2, 7, 11, 11 and 12.
• The best total stays at 11 at house index 3 because robbing it is worse.

Now compare the two ways of solving it. Counting every call, including the ones that fall off the end of the row, plain recursion makes 25 calls for 5 houses, 287 for 10 and 35,421 for 20 (illustrative sizes).¹ Memoization makes 11, 21 and 41.¹ The number of valid choices of houses, counting the empty choice, is 13 for 5 houses, 144 for 10 and 17,711 for 20, which shows how large the search space is.¹

Text description of the diagram

• Plain recursion makes 25 calls for 5 houses and 35,421 calls for 20 houses.
• Memoization makes 11 calls for 5 houses and 41 for 20 houses.

Plain recursion makes 25 calls for 5 houses and 35,421 calls for 20 houses.¹ Memoization makes 11 calls for 5 houses and 41 for 20 houses.¹

Finally, run the wrong recurrence from Step 3 on the same array. It returns 20, more than the true best of 12, because its table adds 7, 9, 3 and 1 in turn (16, then 19, then 20), and those houses are neighbors.¹ A total above the correct answer is a quick sign that the recurrence adds a skipped house.

Trade-offs and edge cases

Four ways of writing the solution trade memory for simplicity. Time for the memoized version is linear, as DesignGurus states, and NeetCode's problem page sets a target of O(n) time and O(n) space or better, where n is the number of houses.

Edge cases are cheap to handle. One house returns its value, two houses return the larger of the two, and zero-value houses never hurt the total. NeetCode's copy keeps values non-negative, so skipping is always allowed, and other sites state their own size limits, so read the limits of the version you practise on.

Two variants reuse the idea. In the circular variant the first and last houses are neighbors, so the circular-variant solution runs the linear solver twice, on houses 0 to n minus 2 and on houses 1 to n minus 1, and takes the larger result. In the tree variant, the tree-variant solution returns a pair from each node, the best total with the node and the best without it, and an empty node returns the pair of zeros. If trees are new, start with the lowest common ancestor of a binary tree.

How to answer it in an interview

The spoken structure: state the choice, write the recurrence, name the repeated work and the fix, reduce the space, then say which edge cases you test.

Common mistakes

• "I take the biggest values first." (wrong) Greedy fails on the array [2, 3, 2]: it takes 3 and stops, while the best is 4 from the two outer houses.¹ (right) "Greedy is not safe, so I compare both options at every house."
• "I take every other house." (wrong) On [2, 1, 1, 2] the even positions give 3 and the odd positions give 3, but houses 0 and 3 give 4.¹ (right) "Skipping can cover two houses in a row."
• "The recurrence is the larger of best[i-1] + nums[i] and best[i-2]." (wrong) It adds a house you did not rob. (right) "Skip keeps best[i-1]; rob is nums[i] + best[i-2]."
• "Dynamic programming always needs an array." (wrong) Here only the last two values matter. (right) "Two variables give constant space."

Follow-up questions

What is the time and space complexity of house robber?

The table or two-variable solution visits each house once, so the time is linear in the number of houses. The table needs linear space and the two-variable version needs constant space.

How do you solve house robber in constant space?

Keep two variables, the best total one house back and two houses back, and update them in one pass as in the code in Step 4. No array is stored because each step reads only those two values.

Why does a greedy approach fail on house robber?

A greedy pick of the largest value can block two good neighbors. On [2, 3, 2] greedy returns 3 while the best is 4, as the common mistakes show.¹

What if the houses are in a circle?

Run the linear solver on houses 0 to n minus 2 and again on houses 1 to n minus 1, then take the larger result, because the first and last houses cannot both be robbed.

How do you find which houses were robbed?

Keep the full table, then walk back from the end. If best[i] equals best[i-1], house i was skipped; otherwise it was robbed and you jump to index i minus 2.

How does the NeetCode version of house robber differ?

NeetCode's version is the same problem with its own limits, between 1 and 100 houses and values from 0 to 100 as of October 2026. The method does not change. For more array patterns see subarray sum equals k and the monotonic stack.

Sources

1. 198. House Robber (problem statement) - LeetCode — LeetCode, 26 Oct 2026
2. House Robber (problem statement, hints, constraints) - NeetCode — NeetCode, 26 Oct 2026
3. House Robber II solution (circular variant, split into two runs) - NeetCode — NeetCode, 26 Oct 2026
4. LeetCode 198 House Robber Solution and Explanation - NeetCode — NeetCode, 26 Oct 2026
5. 198. House Robber - Detailed Explanation - DesignGurus — DesignGurus, 26 Oct 2026
6. 198. House Robber - Leetcode Solution - AlgoMap — AlgoMap, 26 Oct 2026
7. House Robber (circular variant) - NeetCode — NeetCode, 26 Oct 2026
8. 337. House Robber (tree variant) - NeetCode — NeetCode, 26 Oct 2026