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

House Robber II – Solution & Complexity

Interview solutions
/
House Robber II

Solution Walkthrough

  1. Step 1: Why the circle matters

    • In the linear House Robber you may take any non-adjacent subset.
    • Here house 0 and house n-1 are neighbors too, so you can never rob both of them.
    • A single house is a special case: just return it.

  2. Step 2: Split into two linear problems

    • Either you skip the last house or you skip the first house (you cannot keep both).
    • So the answer is the better of robbing houses 0..n-2 and robbing houses 1..n-1, each solved as an ordinary linear House Robber.
    • Here is a first version that fills an explicit DP array for each range.
    def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    def rob_range(arr: list[int]) -> int:
        n = len(arr)
        if n == 0:
            return 0
        if n == 1:
            return arr[0]
        dp = [0] * n
        dp[0] = arr[0]
        dp[1] = max(arr[0], arr[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])
        return dp[-1]

    return max(rob_range(nums[:-1]), rob_range(nums[1:]))

  3. Step 3: Collapse the linear pass to O(1) space

    • The linear recurrence best[i] = max(best[i-1], best[i-2] + arr[i]) only needs the previous two results.
    • Replace the DP array with two rolling variables and reuse that helper on both ranges.

  4. Step 4: Optimal two-pass solution

    • robRange scans a slice keeping prevOne and prevTwo.
    • Call it on nums[:-1] and nums[1:], then take the maximum. Handle the length-1 street before slicing so neither range becomes empty in a way that drops the only house.
    def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    def rob_range(arr: list[int]) -> int:
        prev_two, prev_one = 0, 0
        for value in arr:
            prev_two, prev_one = prev_one, max(prev_one, prev_two + value)
        return prev_one

    return max(rob_range(nums[:-1]), rob_range(nums[1:]))

  5. Step 5: Dry run

    Trace nums = [1,2,3,1].

    • Range [1,2,3] (drop the last house): best loot is 4 by robbing 1 and 3.
    • Range [2,3,1] (drop the first house): best loot is 3 (either 3 alone or 2 + 1).
    • Answer is max(4, 3) = 4.

  6. Step 6: Common mistakes and follow-ups

    • Forgetting the length-1 case and slicing into two empty ranges, which returns 0 instead of the single house.
    • Trying to write one circular recurrence with a flag; the two-pass reduction is simpler and less error-prone.
    • Double-counting by allowing both house 0 and house n-1.
    • Follow-up: how would you also return which houses were robbed, not just the total?

  7. Step 7: Edge cases to test mentally

    • One house: return it directly.
    • Two houses: they are adjacent on both sides, so take the larger.
    • The wrap neighbor can make a locally greedy pick wrong, so always compare both ranges.

  8. Step 8: Final full solution and complexity

    Reduce the circle to two linear passes and keep only rolling state in each. Time is O(n) and extra space is O(1).

    def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    def rob_range(arr: list[int]) -> int:
        prev_two, prev_one = 0, 0
        for value in arr:
            prev_two, prev_one = prev_one, max(prev_one, prev_two + value)
        return prev_one

    return max(rob_range(nums[:-1]), rob_range(nums[1:]))

FAQ

See also

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