How to Solve: House Robber – Complete Guide for FAANG Interviews

How to Solve: House Robber – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 dynamic programming interviews—master it, and you’ll prove you can break down complex decisions into optimal subproblems, a skill every top-tier company tests."

? WHAT YOU NEED TO KNOW FIRST

Before tackling House Robber, ensure you understand: 1. Dynamic Programming (DP) Basics – Memoization, tabulation, and state transitions. 2. Recursion with Memoization – How to cache results to avoid recomputation. 3. Greedy vs. DP Trade-offs – Why greedy fails here (e.g., robbing every other house isn’t always optimal).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental checklist for every House Robber problem:

1. Clarify the Problem
2. Can you rob adjacent houses? (No, triggers alarm.)
3. Is the street linear or circular? (Start with linear, then extend.)

4. What’s the input size? (Small: recursion. Large: DP.)

5. Define the DP State

6. dp[i] = max money robbed up to house i (0-indexed).

7. Why? Because the decision at i depends on i-1 and i-2.

8. Write the Recurrence Relation

9. Option 1: Skip i → dp[i] = dp[i-1]
10. Option 2: Rob i → dp[i] = dp[i-2] + nums[i]

11. Final: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

12. Handle Base Cases

13. dp[0] = nums[0] (only one house)

14. dp[1] = max(nums[0], nums[1]) (two houses)

15. Implement Top-Down (Memoization) or Bottom-Up (Tabulation)

16. Top-down: Recursion + cache (easier to debug).

17. Bottom-up: Iterative DP (faster, less stack overflow).

18. Optimize Space

19. Replace dp array with two variables (prev1, prev2).

20. Test Edge Cases

21. Empty input, single house, two houses, all houses equal.

22. Extend to Follow-Ups

23. Circular street? → Solve two linear problems (skip first or last house).
24. Tree of houses? → Post-order DFS with memoization.

? WORKED EXAMPLES

Example 1 – Basic: Linear Street

Problem: Given an array nums where nums[i] is the money in house i, return the max money you can rob without alerting the police (no adjacent houses).

Framework Walkthrough: 1. Clarify: Linear street, no adjacent houses. 2. DP State: dp[i] = max money up to house i. 3. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). 4. Base Cases:
- dp[0] = nums[0]
- dp[1] = max(nums[0], nums[1]) 5. Implementation (Bottom-Up):
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1] 6. Space Optimization:
python
def rob(nums):
prev1, prev2 = 0, 0
for num in nums:
curr = max(prev1, prev2 + num)
prev2, prev1 = prev1, curr
return prev1 7. Complexity:
- Time: O(n), Space: O(1) (optimized). 8. Why This Works:
- The recurrence captures the two choices at each house (rob or skip), and the DP table ensures we never recompute subproblems.

Example 2 – Medium: Circular Street

Problem: Houses are arranged in a circle. First and last houses are adjacent.

Framework Walkthrough: 1. Clarify: Circular street → cannot rob both first and last house. 2. Key Insight: Solve two linear problems:
- Rob houses 0 to n-2 (skip last house).
- Rob houses 1 to n-1 (skip first house). 3. Implementation:
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
def linear_rob(nums):
prev1, prev2 = 0, 0
for num in nums:
curr = max(prev1, prev2 + num)
prev2, prev1 = prev1, curr
return prev1
return max(linear_rob(nums[:-1]), linear_rob(nums[1:])) 4. Complexity:
- Time: O(n), Space: O(1) (two passes). 5. Why This Works:
- The circular constraint is reduced to two linear problems, each solvable with the basic DP approach.

Example 3 – Hard: House Robber III (Tree of Houses)

Problem: Houses are arranged in a binary tree. Robbing a parent prevents robbing its children.

Framework Walkthrough: 1. Clarify: Tree structure → no linear adjacency. 2. DP State: Return a tuple (rob_current, skip_current) for each node.
- rob_current = node.val + skip_left + skip_right
- skip_current = max(rob_left, skip_left) + max(rob_right, skip_right) 3. Implementation (Post-Order DFS + Memoization):
python
def rob(root):
def dfs(node):
if not node:
return (0, 0)
left = dfs(node.left)
right = dfs(node.right)
rob_current = node.val + left[1] + right[1]
skip_current = max(left) + max(right)
return (rob_current, skip_current)
return max(dfs(root)) 4. Complexity:
- Time: O(n), Space: O(n) (recursion stack). 5. Why This Works:
- The tuple captures both choices (rob or skip) at each node, and DFS ensures we process children before parents.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Here’s your 60-second cheat sheet for House Robber: 1. Linear Street? Use DP with dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Optimize space with two variables. 2. Circular Street? Split into two linear problems (skip first or last house). 3. Tree of Houses? Post-order DFS with a tuple (rob, skip) for each node. 4. Edge Cases: Always check empty input, single house, and two houses. 5. Follow-Ups: Expect circular or tree variants—practice them!

Remember: DP is about choices and subproblems. If you can define the state and recurrence, you’ve got this. Now go crush that interview!

? Final Notes

• Practice Variations: LeetCode 198 (Linear), 213 (Circular), 337 (Tree).
• Time Yourself: Aim for <15 minutes per problem in mock interviews.
• Whiteboard First: Always sketch the DP table or tree before coding.

This framework is battle-tested—use it, and you’ll solve House Robber problems with confidence. ?