Data Structures & Algorithms › Dynamic Programming — 1D
💡
Exercise 124

House Robber 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #198: House Robber — one of the best problems to learn DP! 🏠

💡 Think of it like this: You're a robber looking at a row of houses, each with some money. But there's an alarm — if you rob two houses that are next to each other, the police come! How do you maximize your loot?

# Example: nums = [2, 7, 9, 3, 1] # Rob house 1 (2) + house 3 (9) + house 5 (1) = 12 # OR rob house 2 (7) + house 4 (3) = 10 # Best = 12

The DP Insight: At each house, you have exactly 2 choices:

  • 🏃 Skip this house → your profit = whatever you had at the previous house
  • 💰 Rob this house → your profit = money here + what you had 2 houses ago (can't rob adjacent!)
  • Take the maximum of these two choices

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

💭 Time to code! Use the step-by-step approach described above. Don't peek at the solution — try first! 🚀

Step-by-step trace for [2, 7, 9, 3, 1]:

  • House 0 ($2): max(0, 0+2) = 2. prev2=0, prev1=2
  • House 1 ($7): max(2, 0+7) = 7. prev2=2, prev1=7
  • House 2 ($9): max(7, 2+9) = 11. prev2=7, prev1=11
  • House 3 ($3): max(11, 7+3) = 11. prev2=11, prev1=11
  • House 4 ($1): max(11, 11+1) = 12 ✓

Complexity: Time O(n), Space O(1). Clean!

📋 Instructions
Find maximum amount you can rob. nums = [2,7,9,3,1]
At each house: max(skip it = prev1, rob it = prev2 + current). Use two variables to track the max profit at previous two positions. O(n) time, O(1) space.
⚠️ Try solving it yourself first — you'll learn more!
def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    
    # Only need previous two values (O(1) space!)
    prev2 = 0   # max profit 2 houses ago
    prev1 = 0   # max profit at previous house
    
    for num in nums:
        current = max(prev1, prev2 + num)  # Skip or rob?
        prev2 = prev1
        prev1 = current
    
    return prev1
🧪 Test Cases
Input
rob([2, 7, 9, 3, 1])
Expected
12
Test case 1
← Previous Next Exercise →
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.
›