House Robber

50.1k
0

An integer array nums describes the money stored in a row of houses, and nums[index] gives the amount at position index.

Robbing two adjacent houses triggers an alarm. Return the maximum money obtainable from a valid selection of non-adjacent houses.

Example 1

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Houses at indices 0, 2, and 4 contribute 2 + 9 + 1 = 12.

Example 2

Input: nums = [5]
Output: 5
Explanation: A single available house contributes the complete amount 5.

Recursion

A small choice drives the whole problem. Taking the current house blocks the previous house, and skipping the current house preserves the best total from the shorter prefix. Exploring both legal choices guarantees coverage of every valid selection.

The state solve(index) represents the maximum money from houses 0 through index. The public method starts at n - 1 because the last index represents the complete row, and each recursive call reduces the row to a smaller prefix.

Algorithm

  • Begin by returning 0 for an empty array because no house can contribute money.

  • Define solve(index) as the best total from houses 0 through index so every call has one clear state meaning.

  • Stop below index 0 with value 0 because no valid house remains in a negative prefix.

  • Return nums[0] at index 0 because only the first house remains available.

  • Calculate the take choice with nums[index] and solve(index - 2) because the adjacent previous house becomes unavailable.

  • Calculate the skip choice with solve(index - 1) because leaving the current house preserves the best shorter-prefix result.

  • Return the larger choice because every valid solution either takes or skips the current house.

  • Start recursion from n - 1 because the final state covers the entire row.

Dry Run

House Robber Recursion

House Robber Recursion

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best total through one index.
int solve(int index, vector<int>& nums) {
// No valid house remains below index 0.
if (index < 0) {
return 0;
}
// Index 0 leaves only the first house.
if (index == 0) {
return nums[0];
}
// Taking the house skips the left neighbor.
int take = nums[index] + solve(index - 2, nums);
// Skipping preserves the prior best total.
int skip = solve(index - 1, nums);
// The larger legal total solves the state.
return max(take, skip);
}
public:
// Returns the best total from the full row.
int rob(vector<int>& nums) {
int n = nums.size();
// Empty input has no money to collect.
if (n == 0) {
return 0;
}
// The last index represents the complete row.
return solve(n - 1, nums);
}
};
// Driver code
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2N), where N is the number of index states, because each state can branch into two choices: take or skip.

Space Complexity: O(N), because the recursion stack can contain at most N active calls along the deepest path.

Memoization

Direct recursion reaches the same prefix through several choice paths. Recalculating a solved prefix adds work without adding new information.

A dp array stores the answer for each solve(index) state. A cached value returns immediately, and every uncached state keeps the same take-or-skip decision used by recursion.

Algorithm

  • Begin by returning 0 for an empty array because no state exists for recursion.

  • Create a dp array filled with -1 so every untouched index clearly marks an unsolved state.

  • Keep solve(index) as the best total through index so memoization preserves the recursive state meaning.

  • Handle negative and zero indices as recursion base cases because the boundary values remain unchanged.

  • Return dp[index] after a cache hit because the same prefix already has a complete answer.

  • Calculate take and skip choices with the original recursive calls because memoization changes storage rather than the decision.

  • Store the larger choice in dp[index] so later paths can reuse the solved state.

  • Start from n - 1 because the final index still represents the complete row.

Dry Run

House Robber Memoization

House Robber Memoization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the cached best total through one index.
int solve(
int index,
vector<int>& nums,
vector<int>& dp
) {
// No valid house remains below index 0.
if (index < 0) {
return 0;
}
// Index 0 leaves only the first house.
if (index == 0) {
return nums[0];
}
// A cached value avoids repeated state work.
if (dp[index] != -1) {
return dp[index];
}
// Taking the house skips the left neighbor.
int take = nums[index] + solve(
index - 2, nums, dp
);
// Skipping preserves the prior best total.
int skip = solve(index - 1, nums, dp);
// The larger legal total is cached for reuse.
dp[index] = max(take, skip);
return dp[index];
}
public:
// Returns the best total from the full row.
int rob(vector<int>& nums) {
int n = nums.size();
// Empty input has no money to collect.
if (n == 0) {
return 0;
}
// Minus one marks every state as unsolved.
vector<int> dp(n, -1);
// The last index represents the complete row.
return solve(n - 1, nums, dp);
}
};
// Driver code
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of index states, because each state is computed once and performs constant work.

Space Complexity: O(N), because the dp array stores N values and the recursion stack can contain up to N active calls.

Tabulation

Memoization still depends on recursive calls and a call stack. Tabulation writes the same prefix answers directly from left to right and removes recursive control flow.

The state dp[index] keeps the maximum money from houses 0 through index. Increasing index order guarantees ready values for dp[index - 1] and dp[index - 2] before the current state is calculated.

Algorithm

  • Begin by returning 0 for an empty array because no table entry can represent an absent house.

  • Create a dp array of size n so every index stores the best total for the matching prefix.

  • Set dp[0] = nums[0] because the first prefix contains only one available house.

  • Move from index 1 to n - 1 because both required smaller states must be ready before each update.

  • Build the take choice from nums[index] and dp[index - 2], using 0 near the boundary because no earlier non-adjacent house exists.

  • Read the skip choice from dp[index - 1] because leaving the current house keeps the previous best total.

  • Store the larger choice in dp[index] and return dp[n - 1] because the last table entry represents the complete row.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the best total from the full row.
int rob(vector<int>& nums) {
int n = nums.size();
// Empty input has no table state.
if (n == 0) {
return 0;
}
// Each entry stores one prefix answer.
vector<int> dp(n, 0);
dp[0] = nums[0];
// Left-to-right order prepares smaller states.
for (int index = 1; index < n; index++) {
int take = nums[index];
// Index 1 has no earlier valid prefix.
if (index > 1) {
// Taking uses the prior non-adjacent state.
take += dp[index - 2];
}
// Skipping keeps the previous prefix answer.
int skip = dp[index - 1];
// The larger legal total fills the current state.
dp[index] = max(take, skip);
}
// The last entry represents the complete row.
return dp[n - 1];
}
};
// Driver code
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of houses, because each prefix state is computed once with constant work.

Space Complexity: O(N), because the dp array stores one value for each house, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation reveals a small dependency. The current state uses only the previous prefix answer and the previous non-adjacent prefix answer, so older table entries never return to the calculation.

Variables previous and secondPrevious replace dp[index - 1] and dp[index - 2]. After current selects the larger legal choice, both retained states shift forward in the same order as the table.

Algorithm

  • Begin by returning 0 for an empty array because no retained state can represent an absent house.

  • Store 0 in secondPrevious and nums[0] in previous so both base states match the tabulation boundary.

  • Move from index 1 to n - 1 because each new prefix depends only on the two retained earlier values.

  • Calculate take as nums[index] + secondPrevious because selecting the current house allows only the previous non-adjacent total.

  • Keep skip as previous because leaving the current house preserves the best total through the preceding index.

  • Set current to the larger choice because every valid prefix either takes or skips the current house.

  • Shift previous into secondPrevious, shift current into previous, and return previous because the final retained value represents the complete row.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the best total from the full row.
int rob(vector<int>& nums) {
int n = nums.size();
// Empty input has no retained state.
if (n == 0) {
return 0;
}
// Two values match the first two DP boundaries.
int secondPrevious = 0;
int previous = nums[0];
// Each index needs only two earlier states.
for (int index = 1; index < n; index++) {
// Taking uses the prior non-adjacent total.
int take = nums[index] + secondPrevious;
// Skipping keeps the previous prefix total.
int skip = previous;
// Current stores the larger legal choice.
int current = max(take, skip);
// Retained states shift toward the next index.
secondPrevious = previous;
previous = current;
}
// Previous represents the complete row.
return previous;
}
};
// Driver code
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of houses, because each house is processed once with constant work.

Space Complexity: O(1), because only two previous DP values and one current value are maintained instead of the complete dp array.

Interview follow-up Questions

No. The alarm rule rejects every selection containing neighboring houses.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0