House Robber - Video Solutions

Problem Overview: You are given an array where each element represents money stored in a house along a street. Adjacent houses cannot be robbed on the same night because they trigger an alarm. The goal is to compute the maximum amount of money you can steal without robbing two neighboring houses.

Approach 1: Dynamic Programming - Iterative DP Array (O(n) time, O(n) space)

This problem fits the classic dynamic programming pattern where each decision depends on previous optimal results. Define dp[i] as the maximum money you can rob from the first i houses. For each house, you either rob it or skip it. If you rob house i, you add its value to dp[i-2]. If you skip it, you keep dp[i-1]. The recurrence becomes dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Iterate through the array, computing the best outcome at each step.

This approach explicitly stores results for every house, making the logic easy to visualize and debug. It clearly shows how the problem reduces to choosing between two previous states. The tradeoff is extra memory proportional to the number of houses.

Approach 2: Dynamic Programming - Optimized Space (O(n) time, O(1) space)

The DP recurrence only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of maintaining a full array, keep two variables representing these values. As you iterate through the houses, compute the current best value and shift the variables forward.

At each step, calculate current = max(prev1, prev2 + num), where prev1 stores the best result up to the previous house and prev2 stores the best result two houses back. Update the variables as you move forward. This keeps the same decision logic while eliminating the DP array.

This version is the standard optimal solution discussed in interviews. It still performs a single pass through the array and maintains constant memory usage. The algorithm behaves like a rolling dynamic programming window that tracks only the necessary states.

Recommended for interviews: Start by explaining the DP recurrence using the array-based solution since it clearly demonstrates the decision process between robbing and skipping a house. Then optimize it to the constant-space version. Interviewers usually expect the O(n) time, O(1) space solution because it shows strong understanding of dynamic programming state transitions and space optimization.