{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

House Robber – Solution & Complexity

Interview solutions
/
House Robber

Watch: House Robber with dynamic programming

At each house you either rob it (its cash plus the best up to two houses back) or skip it (the best up to the previous house). Take the larger. Two rolling variables are enough: O(n) time, O(1) space.

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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)House Robber II solution (medium)Jump Game solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?