{ }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.
      +----------- wrap-around edge -----------+
  |                                        |
 house 0 -- house 1 -- ... -- house n-2 -- house n-1
    • That single extra edge is the only difference from the linear problem.
    • A single house is a special case: it has no neighbor, so just return it.

  2. Step 2: Split into two linear problems

    • Every valid circular plan leaves out house 0, leaves out house n-1, or leaves out both.
    • So consider two linear ranges:
    nums           = [ 1,  2,  3,  1 ]
index              0   1   2   3
exclude last   :  [1,  2,  3]          houses 0..n-2
exclude first  :      [2,  3,  1]      houses 1..n-1
    • A plan that skips house n-1 is a valid linear plan on 0..n-2; a plan that skips house 0 is valid on 1..n-1; a plan that skips both endpoints fits in either range, so nothing is lost.
    • Conversely, each range omits one endpoint, so no plan chosen inside a range can use the wrap-around edge. Every candidate is a legal circular plan.
    • Therefore the answer is max(robLinear(0..n-2), robLinear(1..n-1)).
    • Here is a first version that fills an explicit DP array for each range. Copying the ranges is fine here because the DP array already costs O(n) space.
    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(lo, hi) scans the inclusive index range lo..hi of the original array, keeping only prevOne and prevTwo.
    • Call it on 0..n-2 (exclude last) and 1..n-1 (exclude first), then take the maximum. Handle the length-1 street first: with one house both ranges are empty and would return 0 instead of the house.
    • Pass index bounds rather than slicing: in Python (nums[1:]), JavaScript (nums.slice(1)) and Ruby (nums[1..]) a slice copies O(n) elements. Go slices and Rust &nums[1..] are views over the same array, so they stay O(1) extra space.
    def rob(nums: list[int]) -> int:
    n = len(nums)
    if n == 1:
        return nums[0]

    def rob_range(lo: int, hi: int) -> int:
        prev_two, prev_one = 0, 0
        for i in range(lo, hi + 1):
            prev_two, prev_one = prev_one, max(prev_one, prev_two + nums[i])
        return prev_one

    return max(rob_range(0, n - 2), rob_range(1, n - 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: both ranges are empty and the function returns 0 instead of the single house.
    • Slicing the input in Python, JavaScript or Ruby and still claiming O(1) extra space; those slices copy the array. Pass index bounds instead.
    • 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 over index ranges 0..n-2 and 1..n-1, keeping only rolling state in each. Time is O(n) and extra space is O(1): every language either passes index bounds (Python, JavaScript, Java, C++, Ruby) or a non-copying slice view (Go, Rust).

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

    def rob_range(lo: int, hi: int) -> int:
        prev_two, prev_one = 0, 0
        for i in range(lo, hi + 1):
            prev_two, prev_one = prev_one, max(prev_one, prev_two + nums[i])
        return prev_one

    return max(rob_range(0, n - 2), rob_range(1, n - 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