{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

House Robber – Solution & Complexity

Interview solutions
/
House Robber

1. Understand the Choice at Each House

  • At each house, you either rob it or skip it.
  • If you rob the current house, you cannot rob the immediately previous one.
  • The goal is the best total after considering all houses.

2. Define the Dynamic Programming State

  • Let dp[i] mean the maximum money obtainable from houses up to index i.
  • For each house, choose between skipping it (dp[i - 1]) or robbing it (dp[i - 2] + nums[i]).
  • The recurrence is dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

3. Optimize the Space

  • The recurrence only needs the previous two results.
  • Store prev_two for dp[i - 2] and prev_one for dp[i - 1].
  • Update them as you move through the array.

4. Update Rolling Values

  • For each amount, compute the best total if this house is included or skipped.
  • current = max(prev_one, prev_two + amount).
  • Then shift the rolling values forward.
def rob(nums):
    prev_two = 0
    prev_one = 0
    for amount in nums:
        current = max(prev_one, prev_two + amount)
        prev_two = prev_one
        prev_one = current
    return prev_one

5. Final Complete Solution

  • This dynamic programming solution considers every house once.
  • Time complexity is O(n).
  • Space complexity is O(1) because only two previous totals are stored.
def rob(nums: list[int]) -> int:
    prev_two = 0
    prev_one = 0

    for amount in nums:
        current = max(prev_one, prev_two + amount)
        prev_two = prev_one
        prev_one = current

    return prev_one

FAQ

See also:

Practice House Robber online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)Jump Game solution (medium)Jump Game II solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?