Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: House Robber
• Main tags: Array, Dynamic Programming

What the problem is really asking

Each house has some amount of money. The thief wants the largest total possible, but robbing two neighboring houses triggers the alarm.

So the real question is:

At every house, is it better to:

• rob this house and therefore skip the previous one, or
• skip this house and keep the best answer seen so far?

That is the entire problem. Once it is framed that way, the dynamic programming recurrence becomes natural.

The key idea

For house i, only two previous results matter:

• the best total up to house i - 1
• the best total up to house i - 2

If the thief robs house i, the previous house cannot be used, so the total becomes:

best_up_to_i_minus_2 + nums[i]

If the thief skips house i, the total stays:

best_up_to_i_minus_1

So the recurrence is:

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

This is optimal because every valid solution for the prefix ending at i must end in exactly one of those two states:

• skip the current house
• rob the current house

There is no third option, so taking the maximum of those two cases is complete.

How to derive the optimal solution

A clean way to derive it is:

1. Start with a tiny example such as [2, 7, 9, 3, 1].
2. At 9, the thief cannot combine it with 7, but can combine it with 2.
3. That means the decision at each position depends on answers from earlier positions, not on raw house values alone.
4. Once the best answer for every prefix is known, the next answer is just a choice between robbing or skipping the current house.

That is classic dynamic programming: solve smaller prefixes, then extend by one house.

Two equivalent ways to think about it

Both of these mental models describe the same algorithm:

• Prefix DP: dp[i] is the best answer using houses 0..i.
• Take-or-skip DP: for each house, compare rob_current versus skip_current.

The second version is usually easier to implement with constant space because the recurrence only needs the previous two answers.

Why constant space is enough

The full dp array works, but it stores more history than necessary.

Since dp[i] depends only on dp[i - 1] and dp[i - 2], the algorithm can keep just two rolling variables:

• best answer up to the previous house
• best answer up to the house before that

That reduces space from O(n) to O(1) while keeping time at O(n).

Complexity

• Time: O(n)
• Space: O(1)

Python solution

from typing import Sequence


def compute_max_non_adjacent_sum(house_values: Sequence[int]) -> int:
    """Return the largest sum that can be built without taking adjacent values."""
    best_up_to_previous_house = 0
    best_up_to_house_before_previous = 0

    for current_house_value in house_values:
        rob_current_house = best_up_to_house_before_previous + current_house_value
        skip_current_house = best_up_to_previous_house
        best_with_current_prefix = max(rob_current_house, skip_current_house)

        # Shift the rolling DP window forward by one house.
        best_up_to_house_before_previous = best_up_to_previous_house
        best_up_to_previous_house = best_with_current_prefix

    return best_up_to_previous_house


class Solution:
    def rob(self, nums: list[int]) -> int:
        """LeetCode entry point."""
        return compute_max_non_adjacent_sum(nums)