Skip to content
Hello Python

House Robber

Interview ProblemIntermediateMediumTabulationArrayDynamic Programming

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

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). Return the maximum amount obtainable when adjacent house indices cannot both be selected.

Starter code

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

alternating-best

{
  "args": [
    [
      2,
      7,
      9,
      3,
      1
    ]
  ]
}

Expected: 12

Wizard outline
  1. 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.

  2. Step 2: Pass the Choose Ends case

    Complete the readable core algorithm for one representative Interview case. Express each prefix optimum as max(skip current, take current plus optimum two positions back).

  3. Step 3: Harden the Alternating Best boundary

    Repair the reviewed boundary and pass the complete submission contract. Every optimal prefix solution either skips the current house and equals previous, or takes it and must combine with the optimum ending before its neighbor. Taking the maximum covers all valid possibilities.

Footguns and prerequisites
  • A greedy choice of the locally larger adjacent value can block a better later combination.
  • dynamic programming
Reviewed references
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 as a complete Interview Problem.

Recommended approach and implementation

Keep two prefix optima: previous and two_back. For each amount, new optimum is max(previous, two_back+amount), then roll the states.

Why it works: Every optimal prefix solution either skips the current house and equals previous, or takes it and must combine with the optimum ending before its neighbor. Taking the maximum covers all valid possibilities.

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.
        """
        two_back = previous = 0
        for amount in nums:
            two_back, previous = previous, max(previous, two_back + amount)
        return previous
Similar exercises