House Robber II

Interview Problem Interview Medium Tabulation Array Dynamic Programming

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.rob(nums). Houses form a circle, so index 0 and the final index are adjacent. Return the maximum amount with no adjacent selected houses.

Starter code

class Solution:
    def rob(self, nums):
        pass

Test cases

three-houses

{
  "args": [
    [
      2,
      3,
      2
    ]
  ]
}

Expected: 3

Wizard outline

Step 1: Initialize Solution.rob
Replace the empty starter with the first real state owned by Solution.rob. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the First And Last Conflict case
Complete the readable core algorithm for one representative Interview case. Every valid solution excludes either the first house or the last, reducing the circle to two paths.
Step 4: Harden the Three Houses boundary
Repair the reviewed boundary and pass the complete submission contract. No circularly valid selection can contain both first and last, so it belongs to at least one of the two linear cases. Each helper optimizes its complete case, and their maximum is therefore the circular optimum.

Footguns and prerequisites

Handle one house separately because both linear slices would otherwise be empty.
dynamic programming

Reviewed references

LeetCode 213 — House Robber II

Practice prerequisites

Advance Dynamic Programming States(opens in a new tab)
Advance Dynamic Programming States isolates state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected. That focused state discipline is required when implementing house robber two as a complete Interview Problem.

Recommended approach and implementation

Run the linear two-state robber DP on nums without its last house and on nums without its first house; return the larger result.

Why it works: No circularly valid selection can contain both first and last, so it belongs to at least one of the two linear cases. Each helper optimizes its complete case, and their maximum is therefore the circular optimum.

class Solution:
    def rob(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if len(nums) == 1: return nums[0]
        def linear(values):
            two_back = previous = 0
            for amount in values:
                two_back, previous = previous, max(previous, two_back + amount)
            return previous
        return max(linear(nums[:-1]), linear(nums[1:]))

Similar exercises

House Robber(opens in a new tab)