Abstract / Summary

You cannot rob two neighboring houses when trying to steal the most money from a row of houses.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (7+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented class implements a dynamic-programming solution for the classic “house robber” problem. The public method rob receives a vector of integers representing the amount of money in each house and returns the maximum sum that can be obtained without robbing two adjacent houses. The core logic resides in the private recursive function dp, which explores the decision space while caching intermediate results to avoid redundant computation.

Key Components

The solution is organized around three main elements: a memoization container, a recursive helper, and the public entry point.

The memoization container is declared as a member variable:

map<int, int> cache;

It maps a starting index to the best achievable sum from that position onward.

The recursive helper dp follows a clear structure. The first guard handles the termination condition when the index exceeds the array bounds:

if (next >= nums.size())
    return 0;

The second guard checks whether the result for the current index has already been computed:

if (cache.count(next) > 0)
    return cache[next];

The core of the algorithm iterates over all possible choices starting from next. For each house i, it adds the house’s value to the optimal result obtained by skipping the next house (i + 2). The loop maintains the maximum of these candidates:

int best = 0;
for (int i = next; i < nums.size(); i++)
{
    auto current = nums[i] + dp(nums, i + 2);
    if (best < current)
        best = current;
}

After the loop, the computed best value is stored in the cache and returned:

cache[next] = best;
return best;

The public method prepares the environment by clearing any previous cache entries and invoking the helper from the first house:

int rob(vector<int>& nums) {
    cache.clear();
    return dp(nums, 0);
}

Edge Cases Handled

The implementation explicitly addresses several boundary conditions:

When the input vector is empty, the initial call to dp receives next == 0 and the size check next >= nums.size() triggers an immediate return of 0. This correctly yields a maximum loot of zero.

When the vector contains a single element, the loop in dp runs once, adding that element’s value to the result of dp(nums, 2). The recursive call reaches the termination guard and returns 0, so the final answer equals the sole house’s amount.

When the vector contains two elements, the loop evaluates both houses individually. Each iteration adds the house’s value to the result of dp called with an index beyond the array, which again returns 0. The maximum of the two values is selected, ensuring that the algorithm respects the non-adjacent constraint.

If the recursion reaches an index that is exactly one past the last element (next == nums.size() - 1), the loop still processes the final house, and the subsequent call to dp(nums, i + 2) safely lands beyond the array, invoking the base case.

Performance Considerations

The use of a map for caching introduces logarithmic lookup and insertion costs, which is a deliberate trade-off for the flexibility of associative containers. Because each distinct starting index is evaluated at most once, the algorithm avoids the exponential blow-up typical of naïve recursive solutions.

The inner loop iterates from the current index to the end of the vector, accumulating the best achievable sum for that segment. Although this results in a quadratic number of total iterations across all distinct next values, the memoization ensures that each sub-problem is solved only once, eliminating repeated work.

Clearing the cache at the beginning of rob guarantees that multiple invocations on different input vectors do not interfere with one another, preserving correctness without incurring additional overhead during the computation itself.

Overall, the design balances simplicity with effective reuse of previously computed results, delivering a solution that scales reasonably for moderate input sizes while maintaining clear and maintainable code structure.

Imagine there is a long row of little houses, and each house has some coins inside. The goal is to collect as many coins as possible, but there is a rule that you cannot take coins from two houses that are right next to each other. If you take coins from the first one, you must skip the second one and go to the third.

The code works by looking at every house one by one to decide if taking those coins leads to the biggest pile in the end. It uses a clever trick called a cache, which is just like a notebook where it writes down the answer for a house after it figures it out once. That way, if it ever needs to know the answer for that same house again, it does not have to do the hard work of counting all over again.

The function starts at the very first house and keeps jumping forward, adding up coins while always skipping the neighbor to follow the rules. It keeps track of the best total it has found so far by comparing the treasures from different paths. When it reaches the end of the street, it knows exactly which plan gives the most coins. The clear command at the start just makes sure the notebook is empty before starting a brand new game of coin collecting.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust	JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq		Python
	gaosq0604		Python
	gouthampradhan			Java
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02					C
	vthwang			Java
	wisdompeak	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality