House Robber

The House Robber problem is about learning how to reason through choices over time when decisions block future options. That makes it a perfect interview question and a clean introduction to dynamic programming.

Problem Statement

You are given an integer array nums where each element represents the amount of money in a house along a street.

You cannot rob two adjacent houses because doing so triggers an alarm.

Return the maximum amount of money you can rob without alerting the police.

1. Clarify Requirements Before Jumping Into Code

Let's start by locking down the rules.

• Input: an integer array nums

• Output: a single integer representing the maximum money I can rob

• Constraint: I cannot rob two adjacent houses

• Order matters since adjacency is based on index

Let's also sanity-check edge cases:

• What if the array is empty?

• What if there’s only one house?

• Are negative numbers allowed? Usually no, but even if they are, skipping is allowed.

2. Identify the Category of the Question

This has one of the hallmarks of a Dynamic Programming problem: optimal substructures. We are attempting to identify a maximum, and in order to calculate that maximum, we need to find the optimal step to take from each house. Finding that optimal step is our subproblem.

3. Consider a Brute-Force Approach to Understand the Problem

The brute-force idea here is to try every possible subset of houses that doesn’t include adjacent indices.

That means:

• For each house, we either rob it or skip it

• We ensure no two robbed houses are adjacent

But this quickly becomes exponential.

• Time complexity: O(2ⁿ)

• Space complexity: O(n) due to recursion

It helps to understand the problem, but it’s not viable.

4. Brainstorm More Solutions

Our brute-force solution attempted to solve the problem by starting from the first house and building upwards. So for our next idea, what if we tried working from the top down?

Let's start again with the key constraint of this problem. When we stand at house i, I have two choices:

• We can rob this house

• We can skip this house

So let's say I'm standing at house i . Thinking top down, what does the choice I make at house i mean about the choices I made before?

• If I choose to rob house i, it means I cannot have robbed i - 1.

• If I choose to skip house i, then I was free to rob whatever houses I wanted up to i - 1.

That's a powerful realization! Having a way to backtrack from house i to 0 shows us that there's a recursive solution here, but we don't need to identify the path backwards - we need the maximum amount of money we can rob. So let's reframe our two choices in terms of maximum money.

Let dp[i] be the maximum money I can rob from houses 0 through i.

At house i, I have two choices:

• We can rob it, which means our maximum at house i equals dp[i - 2] (since we could not have robbed house i-1) + nums[i]

• We can skip it, which means our maximum stays the same as it was in dp[i - 1]

So all we need to do is choose the maximum between those two choices!

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

Now we can iterate through our nums array and build up our solution inside the dp array.

This gives us a solution that is O(n) in time and space complexity.

Now, as one last optimization, we should ask ourselves: do we really need the whole dp array?

A look at our algorithm shows that in actuality, we are only ever referencing two values: dp[i - 1] and dp[i - 2].

That means we don’t actually need the full array. We can collapse this into two variables.

Final approach recap:

• Track maximum money for house i-1 and i-2

• Update greedily using i = max((i - 1), (i - 2) + nums[i])

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute force recursion	O(2ⁿ)	O(n)	Conceptually simple	Too slow
DP array	O(n)	O(n)	Easy to reason about	Extra memory
Space-optimized DP	O(n)	O(1)	Fast, memory efficient	Requires insight

6. Write Pseudocode to Structure Your Thoughts

if nums is empty:
    return 0

prev2 = 0
prev1 = 0

for each num in nums:
    current = max(prev1, prev2 + num)
    prev2 = prev1
    prev1 = current

return prev1

7. Consider Edge Cases

I explicitly account for:

• Empty array → return 0

• One house → return its value

• Two houses → return the max of the two

• Large arrays → ensure linear time

The space-optimized solution naturally handles these.

8. Write Full Code Syntax

public class HouseRobber {

    public static int rob(int[] nums) {
        int prev2 = 0;
        int prev1 = 0;

        for (int num : nums) {
            int current = Math.max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

9. Test Your Code

System.out.println(rob(new int[]{})); // 0
System.out.println(rob(new int[]{5})); // 5
System.out.println(rob(new int[]{2, 7})); // 7
System.out.println(rob(new int[]{2, 7, 9, 3, 1})); // 12
System.out.println(rob(new int[]{1, 2, 3, 1})); // 4

These tests cover empty input, small inputs, and a standard example.

10. Key Lessons to Remember for Future Questions

• Overlapping subproblems and optimization of subproblems are hallmarks of a Dynamic Programming problem.

• Understanding the recursion solution for a DP problem is always a good start but will often by insufficient in terms of time and space complexity.

• When brainstorming other solutions, one trick is to challenge yourself to reframe a bottoms-up approach as top-down one (or vice-versa).

• If you're stuck half-way down an idea, focus on the piece of data you're trying to solve (like maximum money) and see if you reframe your idea in terms of that piece of data.

• Look for ways to optimize space by zeroing in on only the specific pieces of data you need to solve a problem

• And always remember, interviewers want to see clear reasoning more than clever tricks.

Good Luck and Happy Coding!