Picture yourself as a professional robber eyeing a row of houses. Each house holds a known stash of cash (a non‑negative integer). The neighbourhood alarm is wired so that you cannot rob two houses that sit too close together – doing so would trigger the system. The challenge is to maximise your total haul while respecting the spacing rule.
The problem comes in several flavours:
k generalises the rule: robbing house i makes every house up to k steps away off‑limits (k = 1 means only immediate neighbours).You need to write a single function that handles all these scenarios:
def rob(nums: List[int], k: int, circular: bool) -> int:
...
nums – a list of non‑negative integers; the amount of money stored in each house.k – the minimum safe gap between robbed houses. If you rob house i, you may not rob any house with index in [i+1, i+k].circular – when True, houses are arranged in a circle, so house 0 and house n-1 are adjacent and cannot both be robbed.k = 1, circular = False)This is the original “House Robber” problem. With k = 1 and circular = False, the only restriction is that you may not target two neighbouring houses.
# Example 1
nums = [1, 2, 3, 1]
# Output: 4
# Explanation: Take houses at indices 0 and 2 (1 and 3) → total 4.
# Example 2
nums = [2, 7, 9, 3, 1]
# Output: 12
# Explanation: Take houses at indices 0, 2, and 4 (2, 9, and 1) → total 12.
# Example 3
nums = [5, 3, 4, 11, 2]
# Output: 16
# Explanation: Take houses at indices 0 and 3 (5 and 11) → total 16.
nums = [1,2, 3, 1] k = 1 circular = false
4
We have 4 houses with money amounts: [1, 2, 3, 1].
1 <= len(nums) <= 1000 <= nums[i] <= 400When circular = True (and k = 1), the first and last homes are side‑by‑side. Consequently, you cannot rob both house 0 and house n-1.
# Example 1
nums = [2, 3, 2]
# Output: 3
# Explanation: House 0 and house 2 are adjacent in the circle.
# Safest to rob only house 1 → 3.
# Example 2
nums = [1, 2, 3, 1]
# Output: 4
# Explanation: Rob houses 0 and 2 → 1 + 3 = 4.
# Example 3
nums = [1, 2, 3]
# Output: 3
# Explanation: Pick house 2 alone → 3.
The same base constraints on nums apply.
kGeneralise the spacing rule. When circular = False, robbing house i bans houses i+1, i+2, …, i+k. With k = 1 you get the original adjacent‑only behaviour; larger k enforce a wider safety buffer.
# k = 1 (reduces to basic)
nums = [2, 7, 9, 3, 1]
# Output: 12
# Explanation: Rob indices 0, 2, 4 → 2 + 9 + 1 = 12.
# k = 2 (must leave at least two empty houses after a hit)
nums = [5, 1, 3, 6, 7]
# Output: 12
# Explanation: Steal from house 0 (5) then house 4 (7) → 5 + 7 = 12.
# Other combinations: (0,3)=11, (1,4)=8.
The same base constraints apply. In addition, you may assume 1 <= k < n for non‑trivial cases.
In this variant the houses are arranged as a binary tree. Every node stores a monetary value. Robbing two nodes that are directly linked (parent‑child) trips the alarm.
Write a function appropriate for the tree input that returns the maximum amount you can collect without activating the alarm.
# Example 1
# Tree:
# 3
# / \
# 4 5
# Output: 9
# Explanation: Skip the root, rob both children: 4 + 5 = 9.
# Taking the root gives only 3 (children become inaccessible).
# Example 2
# Tree:
# 2
# / \
# 1 3
# /
# 4
# Output: 7
# Explanation: Rob leaf 4 and right child 3 (neither is a parent/child pair) → 4 + 3 = 7.
# Alternates: root + leaf = 6, children only = 4.
nums = [1,2, 3, 1] k = 1 circular = false
4
We have 4 houses with money amounts: [1, 2, 3, 1].