198. House Robber

The House Robber problem is a classic introduction to Dynamic Programming. It is a favorite among interviewers at companies like Google and Meta because it tests your ability to make optimal sequential decisions. While a “greedy” strategy might seem tempting, this problem proves why looking ahead is essential for maximizing rewards.

Problem statement

You are planning a robbery along a straight line of houses. Each house contains a certain amount of money, but there is a security system in place that connects neighboring houses. If two adjacent houses are robbed on the same night, the alarm will be triggered.

You are given an integer array nums, where each element represents the amount of money stored in a house along the street. Your task is to determine the maximum amount of money you can steal while ensuring that no two neighboring houses are robbed.

Return the maximum total amount that can be stolen without triggering the alarm.

Constraints:

• $1 \leq$ nums.length$\leq 100$
• $0 \leq$ nums[i] $\leq 400$

Examples

Intuition

At every house, you face a binary decision: To rob or not to rob?

If you decide to rob the current house, you must add its value to the maximum profit you had from two houses ago. If you skip it, your profit is simply the maximum you had up to the previous house.

Naive approach

A brute force method would use recursion to explore every valid path.

• The logic: A brute-force method treats the street like a decision tree. For every house iii, we ask: “Is it better to rob this house or skip it?”
  • To get the maximum loot at house i, we calculate solve(i) = max(nums[i] + solve(i-2), solve(i-1)).
  • If we rob house $i$, we add its value to the best result from two houses back.
  • If we skip house $i$, we simply take the best result from the previous house.
• The drawback: This leads to an exponential time complexity of $O(2^n)$. Because many subproblems overlap (e.g., calculating the max for the first $3$ houses over and over), this approach will time out for even moderately sized streets.

Optimized approach using Dynamic Programming

We replace the messy recursion with a simple iterative “running total.” Since our decision for the current house only depends on the results of the two immediate previous houses, we don’t need a full array to store everything.

We just use two variables to track the “max loot so far.” As we move from house to house, we update these variables in a single pass. This reduces the complexity from a slow branching tree to a fast, straight line.

Step-by-step algorithm#

1. Initialize: Start with maxTillPrev and maxTillTwoBefore set to $0$. These represent the maximum loot from one house ago and two houses ago, respectively.
2. Loop: Walk down the street house by house, iterating through the nums array.
3. Compare: For each house, calculate a currentMax. This is the maximum of:
   1. Robbing the current house: currentHouseLoot + maxTillTwoBefore
   2. Skipping the current house: maxTillPrev
4. Shift: Move your “memory” forward to prepare for the next house:
   1. maxTillTwoBefore becomes maxTillPrev
   2. maxTillPrev becomes the currentMax we just found.
5. Finalize: After visiting the last house, maxTillPrev holds the maximum possible loot and is our final answer.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 6

Code implementation

Let’s look at the code for this solution below:

def rob(nums):
    # maxTillPrev: Max loot reached including or excluding the house immediately before
    # maxTillTwoBefore: Max loot reached two houses prior
    maxTillPrev = 0
    maxTillTwoBefore = 0

    for currentHouseLoot in nums:
        # Decision: Rob this house (loot + maxTillTwoBefore) or skip it (maxTillPrev)
        currentMax = max(currentHouseLoot + maxTillTwoBefore, maxTillPrev)

        # Shift pointers forward for the next iteration
        maxTillTwoBefore = maxTillPrev
        maxTillPrev = currentMax

    return maxTillPrev


def main():
    testCases = [
        [2, 7, 9, 31, 33, 4, 99, 1, 2, 3, 15, 34, 23, 11, 9, 1, 4], 
        [1, 2, 3, 1], 
        [4, 6, 3, 9, 3, 8, 3], 
        [1, 5, 7, 3, 7, 2, 3], 
        [2, 7, 9, 3, 1]
    ]

    for i, houses in enumerate(testCases, 1):
        print(i, ".  Input nums = ", houses, sep="")
        print("    The maximum robbery is: ", rob(houses), sep="")
        print("-" * 75)

if __name__ == '__main__':
    main()

Time complexity

$O(n)$: We iterate through the array of houses exactly once. Regardless of how much loot is in each house, the time taken increases linearly with the number of houses nnn.

Space complexity

$O(1)$: Instead of maintaining a full DP table of size nnn, we only keep track of the two most recent results (premaxTillPrev and maxTillTwoBefore) at any given time.

Common pitfalls and interview tips

These are common mistakes interviewers often see, along with practical tips to help you explain your reasoning clearly and avoid unnecessary complexity:

• Don’t overcomplicate the state: Many beginners try to create a 2D DP table. Remind the interviewer that you only need the last two states, which saves $O(n)$ space.
• The “All Evens vs. All Odds” trap: Candidates often suggest summing all even-indexed or all odd-indexed houses. Use a counter-example like $[100,1,1,100]$ to show that skipping two houses in the middle is sometimes the winning strategy.
• Base cases: Always clarify how to handle an empty array (should return $0$) or an array with one element (should return that element).