Definition
- No-adjacent rule – you cannot take from two consecutive positions, so taking a house forces skipping its immediate neighbour.
- Recurrence – bestUpTo[i] = max(bestUpTo[i-1], values[i] + bestUpTo[i-2]).
- Rolling variables – only the two most recent states matter, so include and exclude variables replace the full array.
- Fibonacci pattern – each state depends on exactly the two preceding states, mirroring the Fibonacci recurrence structure.
- O(n) time, O(1) space – one pass through the array with two variables.
The National Bank of India plans a branch maintenance schedule where servicing two adjacent branches on the same day is not allowed. Each branch has a benefit value for being serviced. The bank wants the maximum total benefit under the no-adjacent constraint.
Understanding the Concepts
What is the House Thief problem?
Given an array of non-negative numbers representing the value in each house along a street, find the maximum total you can collect without taking from two adjacent houses. This is also known as the Maximum Non-Adjacent Sum problem.
package com.bank.maintenance;
public class HouseThief {
public static long maxNonAdjacentSum(int[] values) {
long include = 0; // best total including current house
long exclude = 0; // best total excluding current house
for (int value : values) {
long newInclude = exclude + value;
long newExclude = Math.max(include, exclude);
include = newInclude;
exclude = newExclude;
}
return Math.max(include, exclude);
}
}
Why does the recurrence work?
At each house you face two choices: skip it or take it. If you skip house i, the best total is whatever you had up to house i-1. If you take house i, you add its value to the best total up to house i-2, because house i-1 is adjacent and must be skipped. The answer is the larger of the two choices. This is what makes it a Fibonacci-style recurrence: each state depends on exactly the two preceding states.
// Recurrence:
// skip(i) = best up to i-1
// take(i) = values[i] + best up to i-2
// bestUpTo(i) = max(skip(i), take(i))
// Fibonacci parallel:
// fib(n) = fib(n-1) + fib(n-2) → depends on two preceding
// best(i) = max(best(i-1), val[i] + best(i-2)) → depends on two preceding
How do the rolling variables work?
Instead of a full array, keep two variables: include (best total that includes the current house) and exclude (best total that excludes it). At each step, compute the new include as the old exclude plus the current value (taking this house means the previous was excluded), and the new exclude as the max of the old include and old exclude (skipping this house means either the previous was taken or not). The answer is max(include, exclude).
package com.bank.maintenance;
public class RollingVarTrace {
public static void trace() {
int[] values = {2, 7, 9, 3, 1};
long incl = 0, excl = 0;
// House 0 (value 2): newIncl=0+2=2, newExcl=max(0,0)=0 → incl=2, excl=0
// House 1 (value 7): newIncl=0+7=7, newExcl=max(2,0)=2 → incl=7, excl=2
// House 2 (value 9): newIncl=2+9=11, newExcl=max(7,2)=7 → incl=11, excl=7
// House 3 (value 3): newIncl=7+3=10, newExcl=max(11,7)=11 → incl=10, excl=11
// House 4 (value 1): newIncl=11+1=12, newExcl=max(10,11)=11 → incl=12, excl=11
// Answer: max(12, 11) = 12 (houses 0, 2, 4: 2+9+1=12)
System.out.println("Max non-adjacent sum: " +
HouseThief.maxNonAdjacentSum(values));
}
}
Max non-adjacent sum: 12
How is this different from the array DP version?
The array version uses dp[i] = max(dp[i-1], values[i] + dp[i-2]). Since each state only reads dp[i-1] and dp[i-2], you can replace the array with two variables, reducing space from O(n) to O(1) while keeping O(n) time.
package com.bank.maintenance;
public class ArrayVersion {
public static long maxSumArray(int[] values) {
if (values.length == 0) return 0;
if (values.length == 1) return values[0];
long[] dp = new long[values.length];
dp[0] = values[0];
dp[1] = Math.max(values[0], values[1]);
for (int i = 2; i < values.length; i++) {
dp[i] = Math.max(dp[i - 1], values[i] + dp[i - 2]);
}
return dp[values.length - 1];
}
// Same result, but O(n) space instead of O(1)
}
What about the circular variant (House Robber II)?
In the circular variant, the first and last houses are also adjacent. The solution runs the linear algorithm twice: once excluding the last house and once excluding the first house, then takes the maximum. This ensures the first and last are never both taken.
package com.bank.maintenance;
import java.util.Arrays;
public class CircularHouseThief {
public static long maxNonAdjacentCircular(int[] values) {
if (values.length == 0) return 0;
if (values.length == 1) return values[0];
// Exclude last house
long option1 = HouseThief.maxNonAdjacentSum(
Arrays.copyOfRange(values, 0, values.length - 1));
// Exclude first house
long option2 = HouseThief.maxNonAdjacentSum(
Arrays.copyOfRange(values, 1, values.length));
return Math.max(option1, option2);
}
public static void main(String[] args) {
int[] values = {2, 3, 2};
System.out.println("Circular max: " + maxNonAdjacentCircular(values)); // 3
}
}
Circular max: 3
What are edge cases?
Edge cases include an empty array (return 0), a single element (return that element), two elements (return the larger), and all elements being zero.
package com.bank.maintenance;
public class EdgeCases {
public static void test() {
System.out.println(HouseThief.maxNonAdjacentSum(new int[]{})); // 0
System.out.println(HouseThief.maxNonAdjacentSum(new int[]{5})); // 5
System.out.println(HouseThief.maxNonAdjacentSum(new int[]{3, 7})); // 7
System.out.println(HouseThief.maxNonAdjacentSum(new int[]{0,0,0})); // 0
}
}
0
5
7
0
What is the time and space complexity?
| Approach | Time | Space | Notes |
|---|---|---|---|
| Array DP | O(n) | O(n) | Full dp array |
| Rolling variables | O(n) | O(1) | Only two variables |
| Brute force | O(2^n) | O(n) | Try all subsets |
What are common mistakes?
The most common mistake is updating include and exclude in place without using temporary variables. If you update include first, the old value is lost before you need it to compute exclude.
package com.bank.maintenance;
public class CommonMistakes {
// WRONG: in-place update loses old values
public static long wrongVersion(int[] values) {
long incl = 0, excl = 0;
for (int v : values) {
incl = excl + v; // incl overwritten!
excl = Math.max(incl, excl); // BUG: uses NEW incl, not old!
}
return Math.max(incl, excl);
}
// CORRECT: use temporary variables
public static long correctVersion(int[] values) {
long incl = 0, excl = 0;
for (int v : values) {
long newIncl = excl + v; // uses old excl
long newExcl = Math.max(incl, excl); // uses old incl
incl = newIncl;
excl = newExcl;
}
return Math.max(incl, excl);
}
}
What should a senior engineer know?
A senior engineer should recognize this as the Fibonacci Numbers DP pattern, mention the circular variant, and note that for banking amounts BigDecimal should replace long. The senior should also explain that this pattern appears in scheduling problems, resource allocation, and any scenario where selecting adjacent items is forbidden.
// Senior points:
// 1. Fibonacci pattern: each state depends on two preceding states
// 2. Circular variant: run twice excluding first/last, take max
// 3. Banking: use BigDecimal for money, not long
// 4. Scheduling: same pattern for non-adjacent task selection
// 5. Extension: weighted interval scheduling generalizes this
Visual Overview
Rolling Variable Trace
=======================
Values: [2, 7, 9, 3, 1]
House Value include exclude newIncl newExcl
───── ───── ─────── ─────── ────────── ──────────
start - 0 0
0 2 0+2=2 max(0,0)=0
2 0
1 7 0+7=7 max(2,0)=2
7 2
2 9 2+9=11 max(7,2)=7
11 7
3 3 7+3=10 max(11,7)=11
10 11
4 1 11+1=12 max(10,11)=11
12 11
Answer: max(12, 11) = 12
Selected: houses 0(2) + 2(9) + 4(1) = 12
Recurrence Dependency
=====================
┌──────┐ ┌──────┐ ┌──────┐
│best │──►│best │──►│best │
│[i-2] │ │[i-1] │ │ [i] │
└──────┘ └──────┘ └──┬───┘
│ │
└───── take i ───────┘
(val[i] + best[i-2])
Each state reads only two predecessors → Fibonacci pattern
→ Two rolling variables suffice → O(1) space
Key Takeaway
House Thief is the maximum non-adjacent sum problem and a clean member of the Fibonacci Numbers DP pattern. At each house you face two choices: skip it and keep the best total up to the previous house, or take it and add its value to the best total from two houses back (since the immediate neighbour is forbidden). The answer is the larger of these two choices, and since each state depends on only the two preceding states, two rolling variables give O(n) time and O(1) space.
The rolling variables are include (best total that includes the current house) and exclude (best total that excludes it). At each step, the new include equals the old exclude plus the current value, and the new exclude equals the max of the old include and old exclude. Using temporary variables during the update is essential to avoid overwriting values before they are read.
At the National Bank of India, the facilities team used this to plan branch maintenance where two adjacent branches could not be serviced on the same day. Each branch carried a benefit value, and the team wanted the maximum total benefit for a day under the no-adjacent constraint. The rolling DP computed the answer in a single pass.
The senior-level extension is the circular variant (House Robber II), where the first and last positions are also adjacent. You solve it by running the linear algorithm twice, once excluding the last element and once excluding the first, then taking the maximum.
Remember one sentence: skip or take at each house, taking means adding to the best from two back, and two rolling variables give O(1) space.
---