How to Explain House Robber in a Coding Interview (Step-by-Step)

House Robber is the second classic DP problem after Climbing Stairs — same two-variable rolling pattern, but with a decision at every step: rob this house or skip it. The key is framing it as a max subproblem and arriving at the clean O(n) O(1) solution.

In this post, you’ll learn exactly how to walk an interviewer through House Robber: the constraint, the recurrence relation, both DP approaches, and the two-variable space optimisation.

Problem Statement

Examples

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

What Is the Problem?

“I need to find the maximum sum of elements in an array such that no two chosen elements are adjacent. I can pick or skip each house — as long as I never pick two houses next to each other.”

Stripping away the story and framing it as a max non-adjacent sum problem immediately points toward DP.

Step 1: Walk Through All Three Approaches

The Key Insight

The Recurrence Relation

Spend time on this formula in the interview — it’s the entire problem:

“dp[i−2] + nums[i] is what we get if we rob house i — we had to skip house i−1 so our previous best is two steps back. dp[i−1] is what we get if we skip house i — we just carry forward the best from one step back. We take the max of both.”

Step 3: Talk Through the Code

Approach 1 — DP Array (mention first, good to explain)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]   # Only one house — rob it

        dp = [0] * len(nums)
        dp[0] = nums[0]              # Base: rob first house
        dp[1] = max(nums[0], nums[1])# Base: best of first two

        for i in range(2, len(nums)):
            # Rob house i: nums[i] + best two steps back
            # Skip house i: carry forward best from one step back
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])

        return dp[-1]  # Max money robbing all n houses

Approach 2 — Two Variables O(1) Space (optimal, lead with this)

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2 = 0   # dp[i-2]: best two houses back (starts at 0)
        prev1 = 0   # dp[i-1]: best one house back  (starts at 0)

        for num in nums:
            # Current best: rob this house or skip it
            curr  = max(num + prev2, prev1)
            prev2 = prev1   # Slide window forward
            prev1 = curr

        return prev1  # prev1 holds the answer after full scan

Point out the initialisation — both variables start at 0, not at any house value. This elegantly handles the base cases without a special check: on the first iteration, max(nums[0] + 0, 0) = nums[0], which is correct.

Visual Walkthrough

Tracing the two-variable solution for nums = [2, 7, 9, 3, 1]:

Final answer: 12 (rob houses 0, 2, 4 → 2 + 9 + 1 = 12)

Now tracing the DP array for the same input to show they match:

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“We visit each house exactly once. At each step we do a constant-time max comparison and two variable updates. We only store two integers regardless of n — O(1) space. This is the rolling window optimisation — recognising that dp[i] only depends on dp[i−1] and dp[i−2], so we don’t need the full array.”

Interview Checklist for House Robber

• Restate — “max sum of non-adjacent elements in an array”
• Strip the story — it’s a max non-adjacent subset sum problem
• Mention brute force O(2ⁿ) and dismiss it
• State the recurrence — dp[i] = max(nums[i] + dp[i−2], dp[i−1])
• Explain both choices clearly — rob this house or skip it
• Show DP array approach first — easier to explain and verify
• Optimise to two variables — only need last two dp values
• Explain why prev2 and prev1 start at 0 — eliminates base case edge handling
• Handle single house and two house edge cases
• State O(n) time and O(1) space
• Ask before coding, don’t just dive in

Related Problems to Practice

If you can solve House Robber cleanly, try these next: