House Robber II (Circular)

📋

Problem

Imagine a thief planning to rob houses arranged in a circle. Because the first and last houses are neighbors, robbing both triggers an alarm. How can the thief maximize loot without alerting the police?

You are a professional robber planning to rob houses along a street arranged in a circle. Each house has a certain amount of money stashed. Adjacent houses have security systems connected, so robbing two adjacent houses will trigger an alarm. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob without alerting the police.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^4

Edge cases: Single house → must rob that houseTwo houses with different amounts → rob the richer oneAll houses have zero money → result is zero

</>

IDE

def rob(nums: list[int]) -> int:public int rob(int[] nums)int rob(vector<int>& nums)function rob(nums)

def rob(nums):
    # Write your solution here
    pass

class Solution {
    public int rob(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int rob(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function rob(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 5Robbing both first and last houses in circular array, violating adjacency constraint.✅ Split problem into two linear DP calls: rob_linear(nums, 0, n-2) and rob_linear(nums, 1, n-1), then take max.

Wrong: 0Not handling single house or empty input cases properly, returning default zero.✅ Add base case checks: if nums is empty return 0; if length 1 return nums[0].

Wrong: Incorrect sum greater than possibleUsing greedy approach that sums largest values without considering adjacency or circular constraint.✅ Use DP with exclusion of first or last house to respect circular adjacency.

Wrong: TLE or timeoutUsing brute force recursion with exponential time complexity.✅ Implement bottom-up or top-down DP with memoization for O(n) time complexity.

✓

Test Cases

Focus on handling edge cases like empty or single-element arrays correctly.

Watch out for common algorithmic traps like greedy approaches or off-by-one errors.

Optimize your solution to linear time and constant space to handle large inputs efficiently.

t1_01basic

Input{"nums":[2,3,2]}

Expected3

⏱ Performance - must finish in 2000ms

Rob house 2 (money = 3), cannot rob house 1 and 3 together because they are adjacent in a circle.

💡 Consider the problem as two linear rob problems excluding either the first or last house.

💡 Use dynamic programming to solve the linear subproblems and take the max result.

💡 Compute max(rob_linear(nums, 0, n-2), rob_linear(nums, 1, n-1)) to handle circular adjacency.

Why it failed: Failed to handle circular constraint correctly; likely robbed both first and last houses. Fix by splitting into two linear DP calls excluding first or last house.

✓ Correctly handled circular adjacency by splitting into two linear DP problems.

t1_02basic

Input{"nums":[1,2,3,1]}

Expected4

⏱ Performance - must finish in 2000ms

Rob houses 1 and 3 (1-based indexing) for total 4; cannot rob both first and last together.

💡 Split the circle into two linear arrays excluding first or last house.

💡 Apply linear DP to each and take the maximum.

💡 Result is max(rob_linear(nums,0,2), rob_linear(nums,1,3)) = max(4,3) = 4.

Why it failed: Incorrectly included both first and last houses; violates circular adjacency. Fix by excluding one end in DP calculation.

✓ Correctly computed max loot by excluding either first or last house.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

No houses to rob, so maximum loot is 0.

💡 Check for empty input and return 0 immediately.

💡 Handle base case where nums length is zero.

💡 Return 0 if nums is empty to avoid errors.

Why it failed: Did not handle empty input; likely caused index error or incorrect output. Fix by returning 0 when nums is empty.

✓ Correctly handled empty input by returning 0.

t2_02edge

Input{"nums":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Only one house to rob, so maximum loot is the amount in that house.

💡 If only one house, rob it directly.

💡 Check for nums length == 1 and return nums[0].

💡 Return nums[0] when length is 1 to handle this base case.

Why it failed: Failed to handle single house case; possibly returned 0 or incorrect value. Fix by returning nums[0] if length is 1.

✓ Correctly handled single house case by returning its value.

t2_03edge

Input{"nums":[0,0]}

Expected0

⏱ Performance - must finish in 2000ms

Both houses have zero money, so maximum loot is 0.

💡 Check that zero values do not cause incorrect sums.

💡 DP should handle zero values gracefully.

💡 Result is zero since no house has money.

Why it failed: Incorrectly returned non-zero value when all houses have zero money. Fix by ensuring DP sums correctly handle zeros.

✓ Correctly returned 0 when all houses have zero money.

t3_01corner

Input{"nums":[2,7,9,3,1]}

Expected12

⏱ Performance - must finish in 2000ms

Cannot rob both first and last houses due to circular adjacency. The best is to rob houses 1, 3, and 5 (2 + 9 + 1 = 12) excluding either first or last house. So max is max(rob_linear(nums, 0, 3), rob_linear(nums, 1, 4)) = max(2+9=11, 7+3+1=11) but actually the max is 12 by robbing houses 1, 3, and 5 when considering the correct DP ranges.

💡 Beware of greedy approach that picks largest values without considering adjacency.

💡 Use DP to consider all combinations excluding first or last house.

💡 Split problem into two linear DP calls and take max to avoid circular adjacency.

Why it failed: Greedy approach failed by summing non-adjacent houses incorrectly. Fix by using DP with exclusion of first or last house.

✓ Correctly avoided greedy trap by using DP and splitting problem.

t3_02corner

Input{"nums":[1,2,3,1,2]}

Expected5

⏱ Performance - must finish in 2000ms

Max loot is 5 by robbing houses 2 and 4 or 3 and 5, respecting circular adjacency.

💡 Check that solution does not treat problem as unbounded knapsack (repeated robbing).

💡 Each house can be robbed at most once; use 0/1 DP approach.

💡 Split into two linear DP problems excluding first or last house.

Why it failed: Mistook problem for unbounded knapsack allowing multiple robs of same house. Fix by ensuring each house is considered once in DP.

✓ Correctly applied 0/1 DP constraint with circular adjacency.

t3_03corner

Input{"nums":[4,1,2,7,5,3,1]}

Expected14

⏱ Performance - must finish in 2000ms

Max loot is 14 by robbing houses 1, 4, and 6 (4 + 7 + 3 = 14) or 2, 4, and 7 (1 + 7 + 1 = 9) but first and last can't both be robbed.

💡 Watch for off-by-one errors in DP indices when excluding first or last house.

💡 Carefully define DP ranges: rob_linear(nums, 0, n-2) and rob_linear(nums, 1, n-1).

💡 Ensure DP recurrence uses correct indices to avoid missing houses.

Why it failed: Off-by-one error caused incorrect DP range leading to missed houses. Fix by correctly setting DP start and end indices.

✓ Correctly handled DP ranges to include all valid houses.

t4_01performance

Input{"nums":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, must complete in O(n) time within 2 seconds.

💡 Use bottom-up DP with O(n) time complexity.

💡 Avoid exponential brute force recursion.

💡 Use space optimized DP to reduce memory usage.

Why it failed: Brute force or exponential recursion causes TLE. Fix by implementing O(n) DP solution.

✓ Solution runs in O(n) time and passes performance constraints.

Practice

1. Given the following code for maxProfit and input prices = [1, 2, 4], what is the value of profit[2] after the last iteration of the outer loop?

easy

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Trace profit and maxDiff arrays

   Initialize profit=[0,0,0], maxDiff=[-1,-1,-1]. At i=1 (price=2): k=2: profit[2]=max(0,2-1)=1, maxDiff[2]=max(-1,0-2)=-1 k=1: profit[1]=max(0,2-1)=1, maxDiff[1]=max(-1,0-2)=-1 At i=2 (price=4): k=2: profit[2]=max(1,4-1)=3, maxDiff[2]=max(-1,1-4)=-1 k=1: profit[1]=max(1,4-1)=3, maxDiff[1]=max(-1,0-4)=-1

2. Step 2: Final profit[2] value

   After last iteration, profit[2] = 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Profit matches max gain from two transactions [OK]

Hint: Track updates to profit and maxDiff carefully [OK]

Common Mistakes:

• Off-by-one in loop indices
• Confusing profit[k] with profit[k-1]

2. What is the time complexity of the space-optimized DP solution for the Best Time -- 2 Transactions problem with input size n and fixed k=2?

medium

A. O(n^2)

B. O(n * k)

C. O(n)

D. O(k^n)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n-1 times, inner loop runs k times (k=2 fixed). So total iterations ~ n*k.

2. Step 2: Simplify complexity with fixed k

   Since k=2 is constant, O(n*k) simplifies to O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to fixed number of transactions [OK]

Hint: Fixed k means linear time, not quadratic [OK]

Common Mistakes:

• Confusing k as variable leading to O(n*k)
• Assuming nested loops always mean O(n^2)

3. What is the time and space complexity of the optimal dynamic programming solution for the unlimited transactions stock problem using the space-optimized state machine approach?

medium

A. Time: O(n^2), Space: O(n) due to nested loops and dp array

B. Time: O(n), Space: O(1) by tracking only current holding and not holding states

C. Time: O(n), Space: O(n) because of recursion stack in memoization

D. Time: O(2^n), Space: O(n) due to exponential recursion without memoization

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the price list (length n), performing constant time operations per iteration -> O(n) time.

2. Step 2: Analyze space complexity

   Only two variables track states (holding, not_holding), no arrays or recursion stack -> O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant state variables confirms O(n) time and O(1) space [OK]

Hint: Space optimized DP uses constant space, not arrays or recursion [OK]

Common Mistakes:

• Confusing recursion stack space with iterative DP
• Assuming DP always uses O(n) space
• Mistaking nested loops for this linear solution

4. The following code attempts to count the number of ways to decode a string. Which line contains a subtle bug that causes incorrect results for inputs containing '0'?

medium

A. if s[i] != '0':

B. curr += prev1 # inside two_digit check

C. if 10 <= two_digit <= 26:

D. prev2, prev1 = prev1, curr

Solution

1. Step 1: Identify two-digit addition logic

   The two-digit check should add prev2, not prev1, because it represents ways two steps back.

2. Step 2: Understand impact on '0' handling

   Adding prev1 instead of prev2 causes overcounting or invalid counts when '0' appears, e.g., '10' or '20'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct two-digit addition uses prev2, not prev1 [OK]

Hint: Two-digit addition must add prev2, not prev1 [OK]

Common Mistakes:

• Confusing prev1 and prev2 in two-digit addition

5. Suppose the problem is modified so that you can reuse the same stock multiple times within a single transaction (i.e., buy and sell multiple times without waiting). Which modification to the DP approach correctly handles this variant?

hard

A. Modify the DP to allow buying again without decrementing transactions_left when holding a stock

B. Increase k to a very large number and use the unlimited transactions solution shortcut

C. Use the same DP but skip updating buy states to avoid multiple buys

D. Use a greedy approach to sum all positive price differences without DP

Solution

1. Step 1: Understand the reuse variant

   Reusing stock within a transaction means multiple buys/sells without reducing transaction count on buys.

2. Step 2: Modify DP state transitions

   Allow buy state updates without decrementing transactions_left, so holding state can be refreshed multiple times per transaction.

3. Step 3: Why other options fail

   Unlimited transactions shortcut ignores transaction limit; skipping buy updates breaks profit calculation; greedy fails with transaction constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct DP modification respects transaction count and allows multiple buys per transaction [OK]

Hint: Allow buy updates without reducing transactions_left [OK]

Common Mistakes:

• Using unlimited transactions shortcut incorrectly
• Skipping buy updates breaks DP correctness