House Robber - Dynamic Programming Java Interview Guide
Learn the House Robber Dynamic Programming problem in Java using recursion, memoization, tabulation, and constant-space optimization with complete code examples, step-by-step dry runs, complexity analysis, common mistakes, production use cases, and interview questions.
Introduction
The House Robber problem is a classic Dynamic Programming problem based on a simple restriction:
You cannot select two adjacent elements.
Although the original story describes houses containing money, the real algorithmic problem is:
Given an array of values,
find the maximum sum of non-adjacent elements.
This problem introduces one of the most important Dynamic Programming decision patterns:
Take the current element
or
Skip the current element
The same decision pattern appears in many interview problems involving:
- Maximum profit
- Non-adjacent selections
- Scheduling with conflicts
- Resource allocation
- Weighted interval choices
- Include-or-exclude decisions
- Knapsack-style optimization
Problem Statement
You are given an integer array nums.
Each element represents the amount of money stored in one house.
A robber wants to steal the maximum possible amount, but cannot rob two adjacent houses because doing so triggers the security system.
Return the maximum amount that can be robbed.
Example 1
Input:
nums = [1, 2, 3, 1]
Output:
4
Explanation:
Rob house 0 → 1
Rob house 2 → 3
Total = 1 + 3 = 4
Robbing houses with values 2 and 1 gives only:
2 + 1 = 3
Therefore, the maximum is:
4
Example 2
Input:
nums = [2, 7, 9, 3, 1]
Output:
12
Explanation:
Rob house 0 → 2
Rob house 2 → 9
Rob house 4 → 1
Total = 2 + 9 + 1 = 12
Example 3
Input:
nums = [5]
Output:
5
There is only one house, so the robber selects it.
Example 4
Input:
nums = []
Output:
0
There are no houses to rob.
Core Intuition
At every house, the robber has two choices.
Choice 1: Rob the Current House
When the robber selects house i, house i - 1 cannot be selected.
Therefore:
Current house value
+
Best answer up to house i - 2
Choice 2: Skip the Current House
When the robber skips house i, the answer remains the best amount available up to house i - 1.
Therefore:
Best answer up to house i - 1
Recurrence Relation
Let:
dp[i]
represent:
Maximum money that can be robbed from houses 0 through i
Then:
dp[i]
=
max(
dp[i - 1],
nums[i] + dp[i - 2]
)
Meaning:
Skip current house
or
Rob current house
Take-or-Skip Visualization
For the array:
[2, 7, 9, 3, 1]
At value 9:
Choice 1: Skip 9
Best so far = 7
Choice 2: Take 9
9 + best before adjacent house
9 + 2 = 11
Choose:
max(7, 11) = 11
Decision Flow
graph TD
Current_House_i["Current House i"] --> Two_Choices["Two Choices"]
Two_Choices["Two Choices"] --> Skip_House_i["├── Skip House i"]
Skip_House_i["├── Skip House i"] --> N_["│"]
N_["│"] --> Answer_best_i_1["│ Answer = best(i - 1)"]
Answer_best_i_1["│ Answer = best(i - 1)"] --> N_["│"]
N_["│"] --> Rob_House_i["└── Rob House i"]
Rob_House_i["└── Rob House i"] --> Answer_nums_i_best_i_2["Answer = nums(i) + best(i - 2)"]
Answer_nums_i_best_i_2["Answer = nums(i) + best(i - 2)"] --> Take_Maximum["Take Maximum"]
Why Is This a Dynamic Programming Problem?
The problem satisfies the two core Dynamic Programming properties.
1. Overlapping Subproblems
The recursive solution repeatedly calculates the same indexes.
Example:
rob(4)
├── rob(3)
│ ├── rob(2)
│ └── rob(1)
│
└── rob(2)
The state:
rob(2)
is calculated more than once.
2. Optimal Substructure
The optimal answer for the current index depends on optimal answers for smaller indexes.
best(i)
=
max(
best(i - 1),
nums[i] + best(i - 2)
)
Approach 1: Brute-Force Recursion
Idea
For every house:
- Rob it and move two positions forward
- Skip it and move one position forward
- Return the maximum of both choices
Recursive State Definition
Let:
robFrom(index)
mean:
Maximum money that can be robbed starting from index
At each index:
robCurrent
=
nums[index] + robFrom(index + 2)
skipCurrent
=
robFrom(index + 1)
Answer:
max(robCurrent, skipCurrent)
Complete Java Code: Brute-Force Recursion
public class HouseRobberRecursion {
public static int rob(int[] houses) {
if (houses == null || houses.length == 0) {
return 0;
}
return robFrom(houses, 0);
}
private static int robFrom(
int[] houses,
int currentIndex
) {
if (currentIndex >= houses.length) {
return 0;
}
int robCurrentHouse =
houses[currentIndex]
+ robFrom(
houses,
currentIndex + 2
);
int skipCurrentHouse =
robFrom(
houses,
currentIndex + 1
);
return Math.max(
robCurrentHouse,
skipCurrentHouse
);
}
public static void main(String[] args) {
int[] houses = {2, 7, 9, 3, 1};
int maximumMoney = rob(houses);
System.out.println(
"Maximum amount robbed: "
+ maximumMoney
);
}
}
Output:
Maximum amount robbed: 12
Step-by-Step Explanation of Recursive Code
Step 1: Validate the Input
if (houses == null || houses.length == 0) {
return 0;
}
When the array is null or empty, there is no money to collect.
Step 2: Begin From the First House
return robFrom(houses, 0);
The recursive exploration starts at index 0.
Step 3: Define the Base Case
if (currentIndex >= houses.length) {
return 0;
}
When the index moves beyond the array, there are no remaining houses.
Therefore, return 0.
Step 4: Rob the Current House
int robCurrentHouse =
houses[currentIndex]
+ robFrom(
houses,
currentIndex + 2
);
When the current house is selected:
- Add its value
- Skip the adjacent house
- Continue from
currentIndex + 2
Step 5: Skip the Current House
int skipCurrentHouse =
robFrom(
houses,
currentIndex + 1
);
When the current house is skipped, continue with the next house.
Step 6: Select the Better Choice
return Math.max(
robCurrentHouse,
skipCurrentHouse
);
The algorithm returns whichever decision produces more money.
Recursive Dry Run
Input:
[2, 7, 9, 3, 1]
At index 0, value 2:
Rob 2
=
2 + robFrom(2)
or:
Skip 2
=
robFrom(1)
Calculate robFrom(2)
Current value:
9
Choices:
Rob 9
=
9 + robFrom(4)
or:
Skip 9
=
robFrom(3)
At index 4:
Rob 1
=
1 + robFrom(6)
=
1
Therefore:
Rob 9 path
=
9 + 1
=
10
Including the first house:
2 + 10 = 12
Calculate robFrom(1)
Current value:
7
Choices include:
7 + robFrom(3)
or:
robFrom(2)
The maximum result from this branch is:
11
Therefore:
max(12, 11) = 12
Recursion Tree
rob(0)
├── Rob house 0
│
│ 2 + rob(2)
│
│ ├── Rob house 2
│ │
│ │ 9 + rob(4)
│ │
│ └── Skip house 2
│
│ rob(3)
│
└── Skip house 0
rob(1)
├── Rob house 1
│
│ 7 + rob(3)
│
└── Skip house 1
rob(2)
Notice that states such as:
rob(2)
rob(3)
are calculated repeatedly.
Complexity of Brute-Force Recursion
| Metric | Complexity |
|---|---|
| Time | O(2ⁿ) |
| Recursion Space | O(n) |
At each house, the algorithm may create two recursive branches.
This approach is useful for discovering the recurrence relation, but it is not suitable for large inputs.
Approach 2: Memoization
Idea
Memoization stores the answer for each index.
Before solving a state, check whether its result has already been calculated.
This eliminates repeated recursive calculations.
Memoization State
memo[index]
=
Maximum money that can be robbed starting from index
Memoization Flow
graph TD
Solve_index["Solve index"] --> Is_memo_index_already_availa["Is memo(index) already available?"]
Is_memo_index_already_availa["Is memo(index) already available?"] --> N_["│"]
N_["│"] --> No["└── No"]
No["└── No"] --> Calculate_rob_and_skip_choic["Calculate rob and skip choices"]
Calculate_rob_and_skip_choic["Calculate rob and skip choices"] --> Store_maximum_in_memo_index["Store maximum in memo(index)"]
Store_maximum_in_memo_index["Store maximum in memo(index)"] --> Return_result["Return result"]
Complete Java Code: Memoization
import java.util.Arrays;
public class HouseRobberMemoization {
public static int rob(int[] houses) {
if (houses == null || houses.length == 0) {
return 0;
}
int[] memo = new int[houses.length];
Arrays.fill(memo, -1);
return robFrom(
houses,
0,
memo
);
}
private static int robFrom(
int[] houses,
int currentIndex,
int[] memo
) {
if (currentIndex >= houses.length) {
return 0;
}
if (memo[currentIndex] != -1) {
return memo[currentIndex];
}
int robCurrentHouse =
houses[currentIndex]
+ robFrom(
houses,
currentIndex + 2,
memo
);
int skipCurrentHouse =
robFrom(
houses,
currentIndex + 1,
memo
);
memo[currentIndex] =
Math.max(
robCurrentHouse,
skipCurrentHouse
);
return memo[currentIndex];
}
public static void main(String[] args) {
int[][] testCases = {
{},
{5},
{1, 2, 3, 1},
{2, 7, 9, 3, 1},
{2, 1, 1, 2}
};
for (int[] houses : testCases) {
int result = rob(houses);
System.out.println(
"Houses: "
+ Arrays.toString(houses)
+ " → Maximum: "
+ result
);
}
}
}
Output:
Houses: [] → Maximum: 0
Houses: [5] → Maximum: 5
Houses: [1, 2, 3, 1] → Maximum: 4
Houses: [2, 7, 9, 3, 1] → Maximum: 12
Houses: [2, 1, 1, 2] → Maximum: 4
Step-by-Step Explanation of Memoization
Step 1: Create the Cache
int[] memo = new int[houses.length];
Each index stores the best result starting from that position.
Step 2: Initialize the Cache
Arrays.fill(memo, -1);
-1 indicates that the state has not been computed.
This works because the problem assumes non-negative house values.
Step 3: Check Cached Results
if (memo[currentIndex] != -1) {
return memo[currentIndex];
}
When the state is already available, return it immediately.
Step 4: Calculate Both Decisions
int robCurrentHouse =
houses[currentIndex]
+ robFrom(
houses,
currentIndex + 2,
memo
);
int skipCurrentHouse =
robFrom(
houses,
currentIndex + 1,
memo
);
Step 5: Cache the Best Answer
memo[currentIndex] =
Math.max(
robCurrentHouse,
skipCurrentHouse
);
The result is stored so the same state is never recalculated.
Memoization Dry Run
Input:
[2, 7, 9, 3, 1]
Initial cache:
Index
0 1 2 3 4
Memo
-1 -1 -1 -1 -1
Calculate index 4:
max(
1 + 0,
0
)
=
1
Cache:
memo[4] = 1
Calculate index 3:
max(
3 + 0,
memo[4]
)
=
max(3, 1)
=
3
Cache:
memo[3] = 3
Calculate index 2:
max(
9 + memo[4],
memo[3]
)
=
max(10, 3)
=
10
Cache:
memo[2] = 10
Calculate index 1:
max(
7 + memo[3],
memo[2]
)
=
max(10, 10)
=
10
Cache:
memo[1] = 10
Calculate index 0:
max(
2 + memo[2],
memo[1]
)
=
max(12, 10)
=
12
Final cache:
[12, 10, 10, 3, 1]
Answer:
12
Complexity of Memoization
| Metric | Complexity |
|---|---|
| Time | O(n) |
| Memoization Array | O(n) |
| Recursion Stack | O(n) |
| Total Space | O(n) |
Each index is solved only once.
Approach 3: Tabulation
Idea
Build the answer iteratively from left to right.
Let:
dp[i]
represent:
Maximum money that can be robbed from the first i houses
This definition uses i as a house count rather than an array index.
Tabulation State
For an input with n houses:
dp[0] = 0
No houses produce no money.
dp[1] = houses[0]
With one house, the best choice is to rob it.
For every later state:
dp[i]
=
max(
dp[i - 1],
houses[i - 1] + dp[i - 2]
)
Complete Java Code: Tabulation
import java.util.Arrays;
public class HouseRobberTabulation {
public static int rob(int[] houses) {
if (houses == null || houses.length == 0) {
return 0;
}
int numberOfHouses = houses.length;
int[] dp =
new int[numberOfHouses + 1];
dp[0] = 0;
dp[1] = houses[0];
for (int houseCount = 2;
houseCount <= numberOfHouses;
houseCount++) {
int currentHouseValue =
houses[houseCount - 1];
int skipCurrentHouse =
dp[houseCount - 1];
int robCurrentHouse =
currentHouseValue
+ dp[houseCount - 2];
dp[houseCount] =
Math.max(
skipCurrentHouse,
robCurrentHouse
);
}
System.out.println(
"DP table: "
+ Arrays.toString(dp)
);
return dp[numberOfHouses];
}
public static void main(String[] args) {
int[] houses = {2, 7, 9, 3, 1};
int result = rob(houses);
System.out.println(
"Maximum amount robbed: "
+ result
);
}
}
Output:
DP table: [0, 2, 7, 11, 11, 12]
Maximum amount robbed: 12
Step-by-Step Tabulation Dry Run
Input:
[2, 7, 9, 3, 1]
Create:
dp = [0, 0, 0, 0, 0, 0]
Base State
dp[0] = 0
No houses:
Maximum = 0
First House
dp[1] = 2
Only one house exists:
Maximum = 2
DP table:
[0, 2, 0, 0, 0, 0]
Process House With Value 7
Skip:
dp[1] = 2
Rob:
7 + dp[0]
=
7 + 0
=
7
Choose:
dp[2] = max(2, 7) = 7
DP table:
[0, 2, 7, 0, 0, 0]
Process House With Value 9
Skip:
dp[2] = 7
Rob:
9 + dp[1]
=
9 + 2
=
11
Choose:
dp[3] = max(7, 11) = 11
DP table:
[0, 2, 7, 11, 0, 0]
Process House With Value 3
Skip:
dp[3] = 11
Rob:
3 + dp[2]
=
3 + 7
=
10
Choose:
dp[4] = max(11, 10) = 11
DP table:
[0, 2, 7, 11, 11, 0]
Process House With Value 1
Skip:
dp[4] = 11
Rob:
1 + dp[3]
=
1 + 11
=
12
Choose:
dp[5] = max(11, 12) = 12
Final table:
[0, 2, 7, 11, 11, 12]
Answer:
12
Tabulation Visualization
House Values
2 7 9 3 1
Best Amount
2 7 11 11 12
At every position:
Best current result
=
maximum of
previous best
and
current value + best two positions earlier
Complexity of Tabulation
| Metric | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) |
Tabulation avoids recursive calls and stack overflow risk.
Approach 4: Space-Optimized Dynamic Programming
Observation
The transition uses only two earlier values:
dp[i - 1]
and
dp[i - 2]
Therefore, the complete DP array is unnecessary.
We only need two variables.
Variable Meaning
previousTwo
=
Best answer up to two houses before
previousOne
=
Best answer up to the previous house
currentBest
=
Best answer including houses processed so far
Complete Java Code: O(1) Space
import java.util.Arrays;
public class HouseRobberOptimized {
public static long rob(int[] houses) {
if (houses == null || houses.length == 0) {
return 0;
}
long previousTwo = 0;
long previousOne = 0;
for (int currentHouseValue : houses) {
long robCurrentHouse =
previousTwo
+ currentHouseValue;
long skipCurrentHouse =
previousOne;
long currentBest =
Math.max(
robCurrentHouse,
skipCurrentHouse
);
previousTwo = previousOne;
previousOne = currentBest;
}
return previousOne;
}
public static void main(String[] args) {
int[][] testCases = {
{},
{5},
{1, 2, 3, 1},
{2, 7, 9, 3, 1},
{2, 1, 1, 2},
{10, 1, 1, 10}
};
for (int[] houses : testCases) {
long result = rob(houses);
System.out.println(
"Houses: "
+ Arrays.toString(houses)
+ " → Maximum amount: "
+ result
);
}
}
}
Output:
Houses: [] → Maximum amount: 0
Houses: [5] → Maximum amount: 5
Houses: [1, 2, 3, 1] → Maximum amount: 4
Houses: [2, 7, 9, 3, 1] → Maximum amount: 12
Houses: [2, 1, 1, 2] → Maximum amount: 4
Houses: [10, 1, 1, 10] → Maximum amount: 20
Step-by-Step Explanation of Optimized Code
Step 1: Initialize Previous States
long previousTwo = 0;
long previousOne = 0;
Before processing any house:
Best amount = 0
Step 2: Process Every House
for (int currentHouseValue : houses)
The loop examines one house at a time.
Step 3: Calculate Rob Choice
long robCurrentHouse =
previousTwo
+ currentHouseValue;
When the current house is robbed, combine its value with the best result from two houses earlier.
Step 4: Calculate Skip Choice
long skipCurrentHouse =
previousOne;
When the current house is skipped, keep the previous best result.
Step 5: Select the Best Result
long currentBest =
Math.max(
robCurrentHouse,
skipCurrentHouse
);
Step 6: Shift the DP States
previousTwo = previousOne;
previousOne = currentBest;
The old previous result becomes the two-step-old result.
The current best becomes the new previous result.
Optimized Dry Run
Input:
[2, 7, 9, 3, 1]
Initial:
previousTwo = 0
previousOne = 0
House Value = 2
Rob:
0 + 2 = 2
Skip:
0
Choose:
2
Update:
previousTwo = 0
previousOne = 2
House Value = 7
Rob:
0 + 7 = 7
Skip:
2
Choose:
7
Update:
previousTwo = 2
previousOne = 7
House Value = 9
Rob:
2 + 9 = 11
Skip:
7
Choose:
11
Update:
previousTwo = 7
previousOne = 11
House Value = 3
Rob:
7 + 3 = 10
Skip:
11
Choose:
11
Update:
previousTwo = 11
previousOne = 11
House Value = 1
Rob:
11 + 1 = 12
Skip:
11
Choose:
12
Final:
previousOne = 12
Answer:
12
State Table
| House Value | Rob Current | Skip Current | Current Best |
|---|---|---|---|
| 2 | 0 + 2 = 2 | 0 | 2 |
| 7 | 0 + 7 = 7 | 2 | 7 |
| 9 | 2 + 9 = 11 | 7 | 11 |
| 3 | 7 + 3 = 10 | 11 | 11 |
| 1 | 11 + 1 = 12 | 11 | 12 |
Complexity Comparison
| Approach | Time | Space | Recommendation |
|---|---|---|---|
| Brute-Force Recursion | O(2ⁿ) | O(n) | Use to explain recurrence |
| Memoization | O(n) | O(n) | Good top-down solution |
| Tabulation | O(n) | O(n) | Good bottom-up solution |
| Space Optimized | O(n) | O(1) | Preferred final solution |
Complete Interview-Ready Java Solution
This version includes:
- Input validation
- Constant-space optimization
longcalculations- Clear variable names
- Multiple automated test cases
import java.util.Arrays;
public final class HouseRobber {
private HouseRobber() {
// Utility class
}
public static long maximumRobberyAmount(
int[] houseValues
) {
if (houseValues == null
|| houseValues.length == 0) {
return 0;
}
long bestTwoHousesBefore = 0;
long bestPreviousHouse = 0;
for (int houseValue : houseValues) {
if (houseValue < 0) {
throw new IllegalArgumentException(
"House values cannot be negative"
);
}
long amountWhenRobbed =
bestTwoHousesBefore
+ houseValue;
long amountWhenSkipped =
bestPreviousHouse;
long bestCurrentAmount =
Math.max(
amountWhenRobbed,
amountWhenSkipped
);
bestTwoHousesBefore =
bestPreviousHouse;
bestPreviousHouse =
bestCurrentAmount;
}
return bestPreviousHouse;
}
public static void main(String[] args) {
verify(new int[]{}, 0);
verify(new int[]{5}, 5);
verify(
new int[]{1, 2, 3, 1},
4
);
verify(
new int[]{2, 7, 9, 3, 1},
12
);
verify(
new int[]{2, 1, 1, 2},
4
);
verify(
new int[]{10, 1, 1, 10},
20
);
System.out.println(
"All test cases passed."
);
}
private static void verify(
int[] houses,
long expected
) {
long actual =
maximumRobberyAmount(houses);
if (actual != expected) {
throw new AssertionError(
"Test failed for "
+ Arrays.toString(houses)
+ ". Expected="
+ expected
+ ", actual="
+ actual
);
}
System.out.println(
Arrays.toString(houses)
+ " → "
+ actual
);
}
}
Output:
[] → 0
[5] → 5
[1, 2, 3, 1] → 4
[2, 7, 9, 3, 1] → 12
[2, 1, 1, 2] → 4
[10, 1, 1, 10] → 20
All test cases passed.
Why Use long?
The total amount may exceed Java's int limit when:
- The input contains many houses
- Individual values are large
- The maximum sum includes many selected houses
Java int maximum:
2,147,483,647
Using long reduces the risk of overflow.
How to Return the Selected Houses
The standard problem asks only for the maximum amount.
An interviewer may ask:
Which houses were selected?
For that variation, maintain a full DP array and reconstruct the choices from right to left.
Complete Java Code: Return Selected House Indexes
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HouseRobberWithSelection {
public record RobberyResult(
long maximumAmount,
List<Integer> selectedIndexes
) {
}
public static RobberyResult rob(
int[] houses
) {
if (houses == null
|| houses.length == 0) {
return new RobberyResult(
0,
List.of()
);
}
int numberOfHouses = houses.length;
long[] dp =
new long[numberOfHouses + 1];
dp[0] = 0;
dp[1] = houses[0];
for (int count = 2;
count <= numberOfHouses;
count++) {
long skipCurrent =
dp[count - 1];
long robCurrent =
houses[count - 1]
+ dp[count - 2];
dp[count] =
Math.max(
skipCurrent,
robCurrent
);
}
List<Integer> selectedIndexes =
new ArrayList<>();
int count = numberOfHouses;
while (count >= 1) {
if (count == 1) {
if (dp[count] > 0) {
selectedIndexes.add(0);
}
break;
}
if (dp[count]
== dp[count - 1]) {
count--;
} else {
int selectedIndex =
count - 1;
selectedIndexes.add(
selectedIndex
);
count -= 2;
}
}
Collections.reverse(
selectedIndexes
);
return new RobberyResult(
dp[numberOfHouses],
List.copyOf(selectedIndexes)
);
}
public static void main(String[] args) {
int[] houses = {
2,
7,
9,
3,
1
};
RobberyResult result =
rob(houses);
System.out.println(
"Maximum amount: "
+ result.maximumAmount()
);
System.out.println(
"Selected indexes: "
+ result.selectedIndexes()
);
}
}
Output:
Maximum amount: 12
Selected indexes: [0, 2, 4]
Selected values:
2 + 9 + 1 = 12
Reconstruction Explanation
Start from the end of the DP table.
At each state:
If dp[i] == dp[i - 1]
the current house was skipped.
Move to:
i - 1
Otherwise, the current house was selected.
Record its index and move to:
i - 2
because the adjacent house cannot be selected.
Edge Cases
Empty Array
[]
Answer:
0
One House
[10]
Answer:
10
Two Houses
[5, 10]
Answer:
10
Select the larger house.
All Equal Values
[5, 5, 5, 5]
Answer:
10
Select either:
indexes 0 and 2
or:
indexes 1 and 3
Increasing Values
[1, 2, 3, 4, 5]
Best selection:
1 + 3 + 5 = 9
Large Values
Use long to avoid integer overflow.
House Robber vs Climbing Stairs
Both problems use one-dimensional Dynamic Programming, but their transitions serve different purposes.
| Feature | Climbing Stairs | House Robber |
|---|---|---|
| Goal | Count paths | Maximize value |
| Transition | Addition | Maximum |
| Formula | dp[i−1] + dp[i−2] |
max(dp[i−1], value + dp[i−2]) |
| Decision | Combine all valid paths | Choose one better decision |
| DP Type | Counting DP | Optimization DP |
House Robber vs 0/1 Knapsack
House Robber resembles a simplified Knapsack problem.
At each element:
Include
or
Exclude
The additional House Robber constraint is:
Selecting one element automatically excludes its adjacent element.
Common Variations
House Robber II
Houses are arranged in a circle.
This means:
First house and last house are adjacent.
Solve two linear problems:
Exclude the last house
and
Exclude the first house
Answer:
max(
rob houses 0 through n - 2,
rob houses 1 through n - 1
)
House Robber III
Houses are arranged as a binary tree.
When a parent node is selected, its immediate children cannot be selected.
This variation combines:
- Tree DFS
- Dynamic Programming
- Include-or-exclude states
Delete and Earn
Selecting a number removes its neighboring values.
After grouping equal numbers, the problem becomes similar to House Robber.
Maximum Sum of Non-Adjacent Elements
This is the direct array version of the same problem without the robbery story.
House Robber II Java Example
public class HouseRobberCircular {
public static long rob(int[] houses) {
if (houses == null
|| houses.length == 0) {
return 0;
}
if (houses.length == 1) {
return houses[0];
}
long excludeLast =
robRange(
houses,
0,
houses.length - 2
);
long excludeFirst =
robRange(
houses,
1,
houses.length - 1
);
return Math.max(
excludeLast,
excludeFirst
);
}
private static long robRange(
int[] houses,
int start,
int end
) {
long previousTwo = 0;
long previousOne = 0;
for (int index = start;
index <= end;
index++) {
long current =
Math.max(
previousOne,
previousTwo
+ houses[index]
);
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}
public static void main(String[] args) {
int[] houses = {2, 3, 2};
System.out.println(rob(houses));
}
}
Output:
3
Production Use Cases
The robbery story is only an abstraction.
The algorithm solves many real-world non-adjacent selection problems.
Advertisement Scheduling
Two adjacent advertisement slots may conflict.
Choose non-adjacent advertisements that maximize revenue.
Server Maintenance
Adjacent servers in a dependency chain may not be shut down simultaneously.
Select the maintenance schedule with the highest operational benefit.
Employee Shift Planning
Adjacent shifts may not be assigned to the same employee.
Choose the most valuable non-conflicting shifts.
Manufacturing
Adjacent machines may not be serviced at the same time.
Maximize the value of selected maintenance tasks.
Investment Planning
Some adjacent investment periods may be mutually exclusive.
Choose periods that maximize return.
Batch Job Scheduling
Neighboring jobs may compete for the same resource.
Select the highest-value set of non-conflicting jobs.
Feature Rollout
Adjacent release windows may not both be used.
Choose rollout windows that maximize expected business impact.
Network Optimization
Adjacent network nodes may not be upgraded simultaneously.
Select nodes that maximize total benefit without violating adjacency constraints.
Common Mistakes
1. Adding Every Alternate House
A greedy pattern such as:
Take indexes 0, 2, 4
does not always produce the correct result.
Example:
[2, 100, 3, 4]
Taking indexes 0 and 2 gives:
5
But the optimal answer is:
100 + 4 = 104
2. Comparing Only Adjacent Values
The problem is not solved by selecting the larger value from each neighboring pair.
Selections affect future decisions.
3. Forgetting the Skip Choice
Every transition must compare:
Skip current
and
Rob current
4. Using dp[i - 1] When Robbing Current
Incorrect:
houses[i] + dp[i - 1]
This may select adjacent houses.
Correct:
houses[i] + dp[i - 2]
5. Incorrect Base Cases
For the full-array DP definition:
dp[0] = 0
dp[1] = houses[0]
6. Accessing dp[1] for an Empty Array
Handle the empty input before initializing the first DP state.
7. Updating Optimized Variables in the Wrong Order
Incorrect:
previousOne = currentBest;
previousTwo = previousOne;
This loses the old previousOne.
Correct:
previousTwo = previousOne;
previousOne = currentBest;
8. Returning the Sum Instead of the Maximum
This is an optimization problem, not a counting problem.
The transition uses:
Math.max(...)
not addition of both branches.
9. Using Exponential Recursion as the Final Answer
Plain recursion is useful for explaining the decision tree, but the final solution should use Dynamic Programming.
10. Ignoring Overflow
Use long when input values or array size may be large.
Interview Problem-Solving Approach
Use the following structure during an interview.
Step 1: Define the State
dp[i]
=
Maximum money from the first i houses
Step 2: Identify the Decision
For the current house:
Rob it
or
Skip it
Step 3: Write the Transition
dp[i]
=
max(
dp[i - 1],
currentHouse + dp[i - 2]
)
Step 4: Define Base Cases
dp[0] = 0
dp[1] = houses[0]
Step 5: Implement Tabulation
Build the answer from left to right.
Step 6: Optimize Space
Since only two previous states are needed, replace the array with two variables.
Step 7: Test Edge Cases
Test:
[]
[5]
[1, 2]
[1, 2, 3, 1]
[2, 7, 9, 3, 1]
Interview Explanation
A clear interview explanation could be:
At every house, I have two choices. I can skip the current house and keep the best amount calculated for the previous house, or I can rob the current house and add its value to the best amount from two houses earlier. Therefore, the recurrence is
dp[i] = max(dp[i−1], nums[i] + dp[i−2]). Since only the previous two states are needed, the space complexity can be optimized fromO(n)toO(1).
Frequently Asked Interview Questions
1. What is the main Dynamic Programming decision in House Robber?
Answer
At every house, decide whether to rob the current house or skip it.
2. What is the recurrence relation?
Answer
dp[i]
=
max(
dp[i - 1],
nums[i] + dp[i - 2]
)
3. Why do we use dp[i - 2] when robbing the current house?
Answer
Because the immediately previous house is adjacent and cannot be robbed.
4. What does dp[i] represent?
Answer
Depending on the chosen definition, it represents the maximum amount obtainable up to index i or from the first i houses.
5. What is the time complexity of brute-force recursion?
Answer
Approximately O(2ⁿ) because every state creates rob and skip branches.
6. What is the time complexity of the DP solution?
Answer
O(n) because every house is processed once.
7. Can the space complexity be reduced?
Answer
Yes. Only the previous two DP states are required, so the space complexity can be reduced to O(1).
8. Why does a greedy approach not work?
Answer
A locally larger house may prevent selecting a combination of future houses with a greater total value.
9. How is House Robber II different?
Answer
The houses form a circle, so the first and last houses are adjacent. Solve two ranges and take the maximum.
10. How can selected house indexes be returned?
Answer
Maintain a DP array and reconstruct the decisions by moving backward from the final state.
11. What real problem does House Robber represent?
Answer
It represents maximizing the total value of non-adjacent or mutually conflicting selections.
12. What is the biggest interview mistake?
Answer
Using dp[i−1] when selecting the current house, which incorrectly permits adjacent selections.
Quick Revision
| Topic | Summary |
|---|---|
| Problem | Maximum sum of non-adjacent values |
| Decision | Rob current or skip current |
| DP State | Best amount up to the current position |
| Transition | max(previous, current + previousTwo) |
| Brute-Force Time | O(2ⁿ) |
| DP Time | O(n) |
| Tabulation Space | O(n) |
| Optimized Space | O(1) |
| Related Problems | House Robber II, House Robber III, Delete and Earn |
| Interview Frequency | ⭐⭐⭐⭐⭐ |
Key Takeaways
- House Robber is a classic take-or-skip Dynamic Programming problem.
- The current house can be selected only with the best answer from two houses earlier.
- The current house can also be skipped while preserving the previous best result.
- This creates the recurrence
dp[i] = max(dp[i−1], nums[i] + dp[i−2]). - Brute-force recursion takes exponential time because it repeats the same states.
- Memoization and Tabulation reduce the time complexity to
O(n). - Since only two previous states are needed, the final solution uses
O(1)additional space. - The same pattern applies to scheduling, resource allocation, investments, maintenance planning, and other non-adjacent selection problems.