House Robber: Take-or-Skip Recurrence
Model the rob/skip decision as a DP recurrence, reduce space to two variables, and extend the solution to circular houses.
House Robber: Take-or-Skip Recurrence is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The House Robber Problem
The House Robber problem asks: given an array of non-negative integers representing the amount of money in each house, find the maximum amount you can rob without robbing two adjacent houses. For example, [2, 7, 9, 3, 1] yields 12 (rob houses 0, 2, 4). This is a classic 1D DP problem where you make a binary decision at each step.
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12Defining the Recurrence
Let dp[i] be the maximum money robbed from the first i+1 houses. At each house i, you have two choices: skip it (take dp[i-1]) or rob it (take nums[i] + dp[i-2]). The recurrence is dp[i] = max(dp[i-1], nums[i] + dp[i-2]). This is the fundamental take-or-skip pattern that appears across many DP problems.
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12Tracing Through the DP Table
For [2, 7, 9, 3, 1], let's trace the table: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. The final answer is dp[4] = 12. Tracing through the table manually confirms the recurrence handles both take and skip correctly at each position.
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])Reducing Space to O(1)
The DP table only ever looks back two positions, so we can replace the entire array with two variables: prev2 (two steps back) and prev1 (one step back). After each iteration, we shift: prev2 = prev1 and prev1 = current. This reduces memory from O(n) to O(1) while keeping time complexity at O(n).
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4Edge Cases to Handle
Always test your solution against edge cases: an empty array (return 0), a single-element array (return that element), and a two-element array (return the maximum of the two). In interviews, mentioning and handling these cases demonstrates thoroughness. The if n == 1 guard prevents index-out-of-bounds when accessing nums[1] for dp[1].
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10House Robber II: Circular Houses
The circular variant (LeetCode 213) places houses in a circle, making the first and last house adjacent. You cannot directly apply the linear recurrence. The key insight is: either you rob the first house and exclude the last, or you exclude the first and include the last. Run the linear house-robber on both sub-arrays and take the maximum.
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4Why Greedy Fails Here
A naive greedy approach might try to always rob the largest available house. However, this fails on inputs like [2, 1, 1, 2]: greedy picks house 0 (value 2) then house 3 (value 2) for total 4, but robbing houses 0 and 2 also gives 3. Wait — in this case greedy works! But try [1, 3, 1, 3, 100]: greedy picks 3 and 3 (indices 1 and 3) for 6, missing the optimal 1+1+100=102. DP is necessary because locally optimal choices do not guarantee a global optimum.
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102Recognising the Take-or-Skip Pattern
The take-or-skip pattern generalises beyond house robber. Any time you scan an array and at each position choose between including the current element (and skipping the previous) or excluding it (and keeping the previous result), you have a take-or-skip DP. Look for constraints like no two adjacent elements or no overlapping intervals as signals to apply this pattern.
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-likeDelete and Earn Variant
Delete and Earn (LeetCode 740) asks: for each number you pick, you earn num × count(num) but must delete all occurrences of num-1 and num+1. This reduces directly to house robber: build an array earn[v] = v × count(v) for all values, then run house robber on this array. Recognising reductions is a key interview skill.
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)House Robber III: Binary Tree
In House Robber III, houses are arranged as a binary tree. You cannot rob a node and its direct parent simultaneously. Define a helper that returns two values: rob(node) → (rob_root, skip_root). If you rob the root, you sum skip values of both children. If you skip the root, you sum the best of each child. This is a post-order DFS with a take-or-skip decision at each node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7Complexity and Interview Discussion
The linear house robber runs in O(n) time and O(1) space with the two-variable optimisation. The circular variant also runs in O(n) time since it calls the linear version twice. The tree variant runs in O(n) time and O(h) space where h is the tree height. In an interview, always state the complexity after coding and mention the space optimisation — it shows you think beyond a first working solution.
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: the take-or-skip recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]), reducing O(n) space to O(1) with two rolling variables, and extending the pattern to circular arrays and binary trees. Next up we explore the Maximum Subarray and Maximum Product Subarray problems using Kadane's algorithm.
Frequently asked questions
Is the “House Robber: Take-or-Skip Recurrence” lesson free?
Yes — the full text of “House Robber: Take-or-Skip Recurrence” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “House Robber: Take-or-Skip Recurrence”?
Model the rob/skip decision as a DP recurrence, reduce space to two variables, and extend the solution to circular houses. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “House Robber: Take-or-Skip Recurrence” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths