3840. House Robber V

MediumArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed and is protected by a security system with a color code.

You are given two integer arrays nums and colors, both of length n, where nums[i] is the amount of money in the i^th house and colors[i] is the color code of that house.

You cannot rob two adjacent houses if they share the same color code. In other words, for any two neighboring houses i - 1 and i, if colors[i - 1] == colors[i], you are not allowed to rob both of them. However, if their colors are different, robbing both is permitted.

Your goal is to choose which houses to rob so that the total amount of money collected is as large as possible, while respecting the color restriction described above.

Return the maximum amount of money you can rob.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

House Robber variant uses DP with two state variables to maximize robbed amount.

Open in Flowchart

Intuition

This problem is a variation of the classic "House Robber" problem. In the original version, the rule is simple: you cannot rob two adjacent houses at all. Here, the restriction is loosened—you can rob two adjacent houses, but only if they have different colors.

When we process houses one by one, the key observation is that the decision for the current house depends on whether we robbed the previous house. So for each house, it helps to track two situations separately:

The maximum money we can have when the current house is not robbed.
The maximum money we can have when the current house is robbed.

Let's call these two values f (current house skipped) and g (current house robbed).

Now think about what happens when we move from house i - 1 to house i:

If we do not rob house i, then it does not matter what we did with house i - 1. The best we can carry forward is simply the better of the two previous states, so the new f becomes max(f, g).
If we do rob house i, we need to decide whether we are allowed to also have robbed house i - 1:
- When colors[i - 1] == colors[i], the two houses share a color, so we cannot have robbed both. That means the previous house must have been skipped. We can only build on the previous f, giving g = f + nums[i].
- When colors[i - 1] != colors[i], the colors differ, so robbing the previous house is allowed. We are free to build on whichever previous state is larger, giving g = max(f, g) + nums[i].

By updating f and g as we walk through the array, each house only needs information from the house right before it. This naturally turns into a simple one-pass dynamic programming with two rolling variables, and the final answer is just max(f, g) after processing all houses.

The starting point is straightforward: before the loop, considering only the first house, f = 0 (we skip it) and g = nums[0] (we rob it).

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Dynamic Programming

We define two variables f and g, where f represents the maximum amount when the current house is not robbed, and g represents the maximum amount when the current house is robbed. Initially, f = 0 and g = nums[0], since for the first house we either skip it (getting 0) or rob it (getting nums[0]). The answer is max(f, g).

Next, we traverse starting from the second house. For each house i, we update f and g based on the color comparison with the previous house:

If the current house has the same color as the previous house (colors[i - 1] == colors[i]), then:
- f is updated to max(f, g) — when we skip the current house, we keep the best of the previous two states.
- g is updated to f + nums[i] — when we rob the current house, the previous house must have been skipped, so we can only build on the old f.
If the current house has a different color from the previous house (colors[i - 1] != colors[i]), then:
- f is updated to max(f, g) — same as above, skipping the current house.
- g is updated to max(f, g) + nums[i] — robbing the current house is allowed regardless of the previous decision, so we build on the better of the old f and g.

A key detail is that both updates must use the old values of f and g at the same time. In Python, the simultaneous assignment f, g = ... evaluates the right-hand side first, so the old values are used correctly without needing temporary variables.

Finally, after processing all houses, we return max(f, g), which gives the maximum money considering both the case where the last house is robbed and where it is not.

Because we only keep two rolling variables and scan the array once, the time complexity is O(n), where n is the number of houses, and the space complexity is O(1).

Example Walkthrough

Let's trace through a small example to see how the two rolling variables f and g evolve.

Input:

nums = [2, 7, 9, 3]
colors = [1, 1, 2, 2]

Recall:

f = max money when the current house is not robbed.
g = max money when the current house is robbed.

Initialization (House 0, nums[0] = 2):

We either skip the first house or rob it.

f = 0 (skip house 0)
g = nums[0] = 2 (rob house 0)

House 1 (nums[1] = 7): Compare colors[0] and colors[1] → 1 == 1 → same color.

Using the old values f = 0, g = 2:

New f = max(f, g) = max(0, 2) = 2 → best result skipping house 1.
New g = f + nums[1] = 0 + 7 = 7 → rob house 1, so house 0 must have been skipped (build on old f = 0).

State after house 1: f = 2, g = 7.

Note: Even though house 0 had 2 dollars, we couldn't add it because both houses share color 1.

House 2 (nums[2] = 9): Compare colors[1] and colors[2] → 1 != 2 → different color.

Using the old values f = 2, g = 7:

New f = max(f, g) = max(2, 7) = 7 → best result skipping house 2.
New g = max(f, g) + nums[2] = 7 + 9 = 16 → rob house 2; different color means we may also have robbed house 1, so build on the better of old f and g (which is 7).

State after house 2: f = 7, g = 16.

Here we robbed both house 1 (7) and house 2 (9) because their colors differ → 16.

House 3 (nums[3] = 3): Compare colors[2] and colors[3] → 2 == 2 → same color.

Using the old values f = 7, g = 16:

New f = max(f, g) = max(7, 16) = 16 → best result skipping house 3.
New g = f + nums[3] = 7 + 3 = 10 → rob house 3, so house 2 must have been skipped (build on old f = 7).

State after house 3: f = 16, g = 10.

Final Answer:

max(f, g) = max(16, 10) = 16.

The optimal plan is to rob house 1 (7) and house 2 (9), since they have different colors, giving a total of 16.

Step	House	nums	color vs prev	f (skip)	g (rob)
Init	0	2	—	0	2
1	1	7	same (1==1)	2	7
2	2	9	diff (1≠2)	7	16
3	3	3	same (2==2)	16	10

Result: max(16, 10) = 16

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def rob(self, nums: List[int], colors: List[int]) -> int:
6        n = len(nums)
7
8        # not_rob: maximum value obtainable when the current house is NOT robbed
9        # rob: maximum value obtainable when the current house IS robbed
10        not_rob, rob = 0, nums[0]
11
12        for i in range(1, n):
13            if colors[i - 1] == colors[i]:
14                # Same color as the previous house:
15                # standard House Robber rule -> cannot rob two adjacent same-color houses.
16                # To rob house i, the previous house must be skipped (use prev not_rob).
17                not_rob, rob = max(not_rob, rob), not_rob + nums[i]
18            else:
19                # Different color from the previous house:
20                # adjacency restriction is lifted, so house i can be robbed
21                # on top of the best state so far (whether prev was robbed or not).
22                not_rob, rob = max(not_rob, rob), max(not_rob, rob) + nums[i]
23
24        # The answer is the best of the two final states.
25        return max(not_rob, rob)
26

1class Solution {
2    /**
3     * Computes the maximum total value that can be robbed.
4     * This is a House Robber variant where the adjacency restriction
5     * depends on whether two neighboring houses share the same color.
6     *
7     * @param nums   the value available at each house
8     * @param colors the color associated with each house
9     * @return the maximum total value obtainable
10     */
11    public long rob(int[] nums, int[] colors) {
12        int n = nums.length;
13
14        // skipPrev: best total when the previous house is NOT robbed.
15        // pickPrev: best total when the previous house IS robbed.
16        long skipPrev = 0;
17        long pickPrev = nums[0];
18
19        for (int i = 1; i < n; i++) {
20            long newPick;
21
22            if (colors[i - 1] == colors[i]) {
23                // Same color as the previous house:
24                // robbing the current house forbids robbing the previous one,
25                // so we must build on the "previous skipped" state.
26                newPick = skipPrev + nums[i];
27            } else {
28                // Different color from the previous house:
29                // the adjacency restriction is lifted, so we may rob the
30                // current house on top of either previous state.
31                newPick = Math.max(skipPrev, pickPrev) + nums[i];
32            }
33
34            // Skipping the current house keeps the best of the two prior states.
35            long newSkip = Math.max(skipPrev, pickPrev);
36
37            // Advance the rolling states for the next iteration.
38            skipPrev = newSkip;
39            pickPrev = newPick;
40        }
41
42        // The answer is the better of robbing or skipping the last house.
43        return Math.max(skipPrev, pickPrev);
44    }
45}
46

1class Solution {
2public:
3    long long rob(vector<int>& nums, vector<int>& colors) {
4        int n = nums.size();
5
6        // notRob: best total when the current house is NOT robbed.
7        // robCur: best total when the current house IS robbed.
8        long long notRob = 0;
9        long long robCur = nums[0];
10
11        for (int i = 1; i < n; ++i) {
12            long long newRobCur;
13
14            if (colors[i - 1] == colors[i]) {
15                // Same color as previous house:
16                // robbing the current house forbids robbing the previous one,
17                // so we must build on the "not robbed" state.
18                newRobCur = notRob + nums[i];
19            } else {
20                // Different color from previous house:
21                // the adjacency constraint is relaxed, so we can extend
22                // from whichever previous state is better.
23                newRobCur = max(notRob, robCur) + nums[i];
24            }
25
26            // Update the "not robbed" state: best of the previous two states.
27            notRob = max(notRob, robCur);
28            // Commit the newly computed "robbed" state.
29            robCur = newRobCur;
30        }
31
32        // The answer is the better of the two final states.
33        return max(notRob, robCur);
34    }
35};
36

1/**
2 * House Robber variant with a color constraint.
3 *
4 * State definitions while iterating:
5 *  - notRobCurr: best total when the current house is NOT robbed.
6 *  - robCurr:    best total when the current house IS robbed.
7 *
8 * Constraint: two adjacent houses with the SAME color cannot both be robbed,
9 * but adjacent houses with DIFFERENT colors are unrestricted.
10 *
11 * @param nums   The amount of money in each house.
12 * @param colors The color of each house.
13 * @returns      The maximum amount of money that can be robbed.
14 */
15function rob(nums: number[], colors: number[]): number {
16    const n: number = nums.length;
17
18    // Best total when the previous house was not robbed.
19    let notRobCurr: number = 0;
20    // Best total when the previous house was robbed (initially just the first house).
21    let robCurr: number = nums[0];
22
23    for (let i = 1; i < n; i++) {
24        const prevBest: number = Math.max(notRobCurr, robCurr);
25
26        if (colors[i - 1] === colors[i]) {
27            // Same color: robbing house i forbids robbing house i-1,
28            // so we must build on notRobCurr (here held by the prior robCurr's "skip" value).
29            [notRobCurr, robCurr] = [prevBest, notRobCurr + nums[i]];
30        } else {
31            // Different color: no adjacency restriction,
32            // so we can rob house i on top of the best result so far.
33            [notRobCurr, robCurr] = [prevBest, prevBest + nums[i]];
34        }
35    }
36
37    // The answer is the best of robbing or not robbing the last house.
38    return Math.max(notRobCurr, robCurr);
39}
40

Time and Space Complexity

Time complexity: O(n), where n is the length of the array nums (i.e., the number of houses). The algorithm iterates through the array once with a single loop from index 1 to n - 1, performing constant-time operations at each step.
Space complexity: O(1). Only a constant number of extra variables (f, g, n, i) are used regardless of the input size, so no additional space proportional to the input is required.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Updated Values Instead of Old Values During State Transition

The most common mistake is updating not_rob and rob sequentially rather than simultaneously. The two state transitions both depend on the old values of not_rob and rob, so updating one before the other corrupts the calculation.

Incorrect Code:

for i in range(1, n):
    if colors[i - 1] == colors[i]:
        not_rob = max(not_rob, rob)   # not_rob is updated first
        rob = not_rob + nums[i]       # BUG: uses the NEW not_rob, not the old one

Here, after not_rob = max(not_rob, rob), the variable not_rob may now hold the old rob value. The next line rob = not_rob + nums[i] then incorrectly builds on this updated value, allowing two adjacent same-color houses to be robbed — violating the problem constraint.

Solution:

Use Python's simultaneous assignment, which evaluates the entire right-hand side before any assignment occurs, so both expressions see the old values:

not_rob, rob = max(not_rob, rob), not_rob + nums[i]

If you are working in a language without tuple assignment (e.g., Java, C++), cache the old values explicitly:

old_not_rob, old_rob = not_rob, rob
not_rob = max(old_not_rob, old_rob)
rob = old_not_rob + nums[i]

Pitfall 2: Failing to Handle the Empty Input or Single-Element Array

The initialization not_rob, rob = 0, nums[0] directly accesses nums[0]. If nums is empty (n == 0), this raises an IndexError.

Solution:

Guard against the empty case before initialization:

if not nums:
    return 0
not_rob, rob = 0, nums[0]

For a single-element array (n == 1), the loop range(1, n) does not execute, and max(not_rob, rob) = max(0, nums[0]) = nums[0] is correctly returned, so no extra handling is needed there.

Pitfall 3: Misinterpreting the Color Constraint as a Reward Rather Than a Restriction

A subtle conceptual error is treating different colors as the only condition under which adjacent houses can be robbed, while forgetting that non-adjacent houses are never restricted by color. The constraint applies only to neighboring houses.

For example, houses at indices 0 and 2 can both be robbed regardless of their colors, because they are not adjacent. The DP naturally handles this because:

In the same-color branch, rob = not_rob + nums[i] builds on the state where house i-1 was skipped — but house i-2 could still have been robbed (captured inside not_rob).

Solution:

Trust that the not_rob state already encodes "house i-1 skipped, but anything before is allowed." Do not add extra color checks comparing non-adjacent houses — this would over-restrict the solution and produce a suboptimal (too small) answer.

Pitfall 4: Confusing the Two State Variables

It is easy to swap the meanings of not_rob and rob, especially when adapting from the classic House Robber problem. Remember:

not_rob = best total when the current house is skipped.
rob = best total when the current house is robbed.

Solution:

Verify the final return is max(not_rob, rob) (covering both endings) rather than just rob, and double-check that the + nums[i] term always appears in the rob transition, never in not_rob.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering

3840. House Robber V

Problem Description

How We Pick the Algorithm

Why Dynamic Programming?

Intuition

Solution Approach

Solution 1: Dynamic Programming

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Using Updated Values Instead of Old Values During State Transition

Pitfall 2: Failing to Handle the Empty Input or Single-Element Array

Pitfall 3: Misinterpreting the Color Constraint as a Reward Rather Than a Restriction

Pitfall 4: Confusing the Two State Variables

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings