The Cautious Burglar

TIP103 Unit 11 Session 1 (Click for link to problem statements)

The Cautious Burglar

Houses along a street hold cash amounts given by nums. A burglar cannot rob two adjacent houses on the same night without triggering an alarm.

Return the maximum amount that can be robbed without ever hitting two neighbors.

def rob(nums):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Dynamic Programming, 1D DP, Decision Making (Rob/Skip)

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does "adjacent" mean here?

  • A: Two houses that sit directly next to each other in nums (indices i and i + 1). The burglar may rob any set of houses as long as no two robbed houses are neighbors.

• Q: Do the robbed houses have to alternate strictly (every other house)?

  • A: No. The burglar can skip two or more houses in a row if that leads to a larger total; the only rule is never robbing two neighbors.

• Q: What should be returned for an empty street?

  • A: If nums is empty, no cash can be taken, so return 0.

HAPPY CASE
Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (cash = 1) and house 2 (cash = 3). They are not adjacent, and 1 + 3 = 4 is the maximum possible.

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 0 (cash = 2), house 2 (cash = 9), and house 4 (cash = 1). Total = 2 + 9 + 1 = 12.

EDGE CASE
Input: nums = []
Output: 0
Explanation: No houses means nothing to rob.

Input: nums = [1, 3, 1, 3, 100]
Output: 103
Explanation: Rob houses 1 and 4 (3 + 100). Robbing every other house starting at index 0 only yields 102, so a greedy alternating strategy fails here.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Optimization Problems with a Rob/Skip Decision at Each Step, we can consider the following approaches:

• Dynamic Programming (1D): The best total up to house i depends only on the best totals up to houses i - 1 and i - 2, giving the recurrence best[i] = max(best[i - 1], best[i - 2] + nums[i]). This is the classic House Robber pattern.
• Recursion with Memoization: A top-down version of the same recurrence; each subproblem (best total for a prefix of houses) is solved once and cached.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Walk down the street one house at a time, tracking two running values: the best haul ending at or before the previous house (prev_one) and the best haul ending at or before the house two back (prev_two). At each house, the burglar either skips it (keeping prev_one) or robs it (adding its cash to prev_two, since the neighbor must then be untouched). Keep whichever choice is larger and slide both trackers forward.

1) Initialize prev_two = 0 and prev_one = 0.
2) For each cash amount in nums:
   a) current = max(prev_one, prev_two + cash)
      - prev_one       -> skip this house
      - prev_two + cash -> rob this house (neighbor excluded)
   b) Shift the window: prev_two = prev_one, prev_one = current.
3) Return prev_one, the best total over all houses.

⚠️ Common Mistakes

• Assuming the answer is to rob every other house (strictly alternating); sometimes skipping two houses in a row is optimal, as in [1, 3, 1, 3, 100].
• Updating prev_two and prev_one in the wrong order, corrupting the recurrence.
• Forgetting the empty-list case, or indexing nums[i - 2] without guarding short inputs in an array-based DP.

4: I-mplement

Implement the code to solve the algorithm.

def rob(nums):
    prev_two = 0  # Best total considering houses up to i - 2
    prev_one = 0  # Best total considering houses up to i - 1
    
    for cash in nums:
        # Either skip this house (keep prev_one)
        # or rob it (prev_two + cash, since the neighbor is off-limits)
        current = max(prev_one, prev_two + cash)
        prev_two, prev_one = prev_one, current
    
    return prev_one

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [1, 2, 3, 1]

  • House 0 (cash 1): current = max(0, 0 + 1) = 1 → (prev_two, prev_one) = (0, 1)
  • House 1 (cash 2): current = max(1, 0 + 2) = 2 → (1, 2)
  • House 2 (cash 3): current = max(2, 1 + 3) = 4 → (2, 4)
  • House 3 (cash 1): current = max(4, 2 + 1) = 4 → (4, 4)
  • Output: 4

• Input: nums = [2, 7, 9, 3, 1]

  • House 0 (cash 2): current = max(0, 0 + 2) = 2 → (0, 2)
  • House 1 (cash 7): current = max(2, 0 + 7) = 7 → (2, 7)
  • House 2 (cash 9): current = max(7, 2 + 9) = 11 → (7, 11)
  • House 3 (cash 3): current = max(11, 7 + 3) = 11 → (11, 11)
  • House 4 (cash 1): current = max(11, 11 + 1) = 12 → (11, 12)
  • Output: 12

• Input: nums = []

  • The loop never runs, so prev_one stays 0.
  • Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of houses (the length of nums).

• Time Complexity: O(N) because we make one constant-time rob/skip decision per house.
• Space Complexity: O(1) because only two rolling variables are kept, regardless of input size.