House Robber II: Maximum Profit from Circular Houses

64k
0

An integer array nums is given, where each value represents money kept in one house. Houses are arranged in a circle, so the first house and the last house are adjacent.

No two adjacent houses can be robbed during the same night. Return the maximum amount of money obtainable.

Example 1

Input: nums = [2, 3, 2]
Output: 3
Explanation: The first and last houses are adjacent, so both houses with value 2 cannot be robbed together. Robbing the middle house gives the maximum amount.

Example 2

Input: nums = [1]
Output: 1
Explanation: A single house has no adjacent conflict, so the only available amount is returned.

Recursion

Start with the small, comforting part of the problem. In a straight row of houses, each house gives two choices: take the current house and move two positions back, or skip the current house and move one position back.

The circle only changes the endpoints. Robbing the first house blocks the last house, and robbing the last house blocks the first house. So the circular problem can be split into two straight-row problems: houses from 0 to n - 2, and houses from 1 to n - 1.

The recursive state solve(index, start) stores the best amount from start through index. The first helper call starts from the ending index of each valid range because the decision is made from right to left until the starting boundary is crossed.

Algorithm

  • Handle the single-house case first because one house has no circular neighbor conflict.

  • Split the circle into ranges 0 through n - 2 and 1 through n - 1 so no range contains both circular endpoints.

  • Define solve(index, start) as the best amount from start through index so every recursive call represents a smaller prefix of one valid range.

  • Stop beyond start with 0, and stop at start with nums[start], because both boundaries have only one possible answer.

  • Compute the skip amount from index - 1 because leaving the current house untouched keeps the previous prefix valid.

  • Compute the take amount from nums[index] plus solve(index - 2, start) because taking a house makes the adjacent previous house unavailable.

  • Return the larger choice for every state, then compare both range answers so the best valid circular total becomes the final answer.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best amount from start through index.
int solve(int index, int start, vector<int>& nums) {
// No house remains inside the active range.
if (index < start) {
return 0;
}
// Only the starting house remains inside the active range.
if (index == start) {
return nums[start];
}
// Skipping keeps the previous house available.
int skip = solve(index - 1, start, nums);
// Taking earns the current amount.
// A two-step jump avoids the adjacent house.
int take = nums[index] + solve(index - 2, start, nums);
// The better valid choice is kept for the current range.
return max(skip, take);
}
public:
// Returns the maximum money obtainable from circular houses.
int rob(vector<int>& nums) {
int n = nums.size();
// A single house has no circular adjacency conflict.
if (n == 1) {
return nums[0];
}
int excludeLast = solve(n - 2, 0, nums);
int excludeFirst = solve(n - 1, 1, nums);
return max(excludeLast, excludeFirst);
}
};
// Driver code
int main() {
vector<int> nums = {2, 3, 2};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of houses, because each non-base recursive state can branch into two choices: take or skip.

Space Complexity: O(N), because the recursion stack can grow to a depth of at most N while processing one linear range.

Memoization

Direct recursion repeats the same range answers. For example, a state such as solve(1, 0) can be reached from multiple branches while the answer remains unchanged.

Memoization adds a dp array for the active linear range. After a state is solved once, the saved value is reused immediately. The circular split and the take-or-skip decision stay exactly the same; only repeated recursion disappears.

Algorithm

  • Handle the single-house case first because one available amount is already the maximum valid total.

  • Process the two allowed ranges separately so the first and last houses never enter the same recursive search.

  • Fill a dp array with -1 for each range so every untouched index clearly marks an unsolved state.

  • Keep solve(index, start) unchanged from recursion so cached states preserve the same prefix meaning and take-or-skip choices.

  • Return 0 beyond start and nums[start] at start because both boundary states have direct answers.

  • Reuse dp[index] after a cache hit because the same range state always produces the same maximum amount.

  • Store the larger take-or-skip amount in dp[index], then compare both range answers so every state is solved once per range.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the cached best amount from start through index.
int solve(int index, int start, vector<int>& nums, vector<int>& dp) {
// No house remains inside the active range.
if (index < start) {
return 0;
}
// Only the starting house remains inside the active range.
if (index == start) {
return nums[start];
}
// A completed state is reused to avoid repeated recursion.
if (dp[index] != -1) {
return dp[index];
}
// Skipping keeps the previous house available.
int skip = solve(index - 1, start, nums, dp);
// Taking earns the current amount.
// A two-step jump avoids the adjacent house.
int take = nums[index] + solve(index - 2, start, nums, dp);
// The better valid choice is saved for future calls.
dp[index] = max(skip, take);
return dp[index];
}
// Solves one range after the circle is split.
// Chosen endpoints prevent a circular clash.
int robLinear(int start, int end, vector<int>& nums) {
vector<int> dp(nums.size(), -1);
return solve(end, start, nums, dp);
}
public:
// Returns the maximum money obtainable from circular houses.
int rob(vector<int>& nums) {
int n = nums.size();
// A single house has no circular adjacency conflict.
if (n == 1) {
return nums[0];
}
int excludeLast = robLinear(0, n - 2, nums);
int excludeFirst = robLinear(1, n - 1, nums);
return max(excludeLast, excludeFirst);
}
};
// Driver code
int main() {
vector<int> nums = {2, 3, 2};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of houses, because each of the two linear ranges contains at most N - 1 states and every state is computed once.

Space Complexity: O(N), because the dp array and recursion stack each require linear space for one range.

Tabulation

Memoization solves a range from the end backward through recursive calls. Tabulation builds the same answers from the start forward.

For one straight range, dp[index] stores the best amount from the range start through index. Processing house index uses dp[index - 1] for the skip amount and nums[index] + dp[index - 2] for the take amount.

The circular part remains unchanged. Solve both straight ranges in table form, then return the larger result.

Algorithm

  • Return the single-house amount directly because no neighboring house can create a circular conflict.

  • Evaluate ranges 0 through n - 2 and 1 through n - 1 so each table represents a valid straight row.

  • Create a dp array for each range so dp[index] can preserve the best amount through every processed house.

  • Set dp[start] = nums[start] because the first allowed house forms the only non-empty choice at the range boundary.

  • Move from start + 1 through end in increasing order so both earlier states are ready before every transition.

  • Read the skip amount from dp[index - 1] and build the take amount from nums[index] plus the available two-step state because adjacent houses cannot be combined.

  • Store the larger choice in dp[index], then compare both range totals so the circular answer keeps the best legal table result.

Dry Run

House Robber II tabulation

House Robber II tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best amount from one straight range.
int robLinear(int start, int end, vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[start] = nums[start];
// Builds each state from already completed previous states.
for (int index = start + 1; index <= end; index++) {
int skip = dp[index - 1];
int previous = 0;
// Check for a two-step state.
// The range boundary prevents invalid access.
if (index - 2 >= start) {
previous = dp[index - 2];
}
// Taking adds the current amount.
// The saved prefix ends before the neighbor.
int take = nums[index] + previous;
dp[index] = max(skip, take);
}
return dp[end];
}
public:
// Returns the maximum money obtainable from circular houses.
int rob(vector<int>& nums) {
int n = nums.size();
// A single house has no circular adjacency conflict.
if (n == 1) {
return nums[0];
}
int excludeLast = robLinear(0, n - 2, nums);
int excludeFirst = robLinear(1, n - 1, nums);
return max(excludeLast, excludeFirst);
}
};
// Driver code
int main() {
vector<int> nums = {2, 3, 2};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of houses, because two linear ranges are processed and each contains at most N - 1 houses.

Space Complexity: O(N), because the dp array stores one value for each house in a range, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation stores the complete dp array, but the current answer needs only two older states. dp[index - 1] gives the skip amount, and dp[index - 2] helps calculate the take amount.

For one straight range, previousOne represents the answer through the previous house, and previousTwo represents the answer through the house before the previous house. The current value is calculated from the same take-or-skip choice, then both variables shift forward.

The circular split stays unchanged. Each of the two ranges is solved with rolling variables, and the larger amount is returned.

Algorithm

  • Return the single-house amount immediately because the only house forms the complete valid answer.

  • Evaluate the two allowed ranges separately so rolling states never combine both circular endpoints.

  • Start each range with previousTwo = 0 and previousOne = nums[start] because both values match the first two DP dependencies.

  • Move from start + 1 through end in increasing order so the rolling variables always describe the two earlier prefix answers.

  • Use previousOne as the skip amount and nums[index] + previousTwo as the take amount because taking the current house must bypass the adjacent house.

  • Calculate current as the larger choice so the best amount through the current house remains available.

  • Shift previousTwo before previousOne, then return previousOne, because the next house needs both old prefix positions in correct order.

Dry Run

House Robber II Space Optimization

House Robber II Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best amount from one straight range.
int robLinear(int start, int end, vector<int>& nums) {
int previousTwo = 0;
int previousOne = nums[start];
// Advances the rolling states across the active range.
for (int index = start + 1; index <= end; index++) {
int skip = previousOne;
int take = nums[index] + previousTwo;
// Calculates current from the better take-or-skip choice.
int current = max(skip, take);
// Shifts both saved states forward for the next house.
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}
public:
// Returns the maximum money obtainable from circular houses.
int rob(vector<int>& nums) {
int n = nums.size();
// A single house has no circular adjacency conflict.
if (n == 1) {
return nums[0];
}
int excludeLast = robLinear(0, n - 2, nums);
int excludeFirst = robLinear(1, n - 1, nums);
return max(excludeLast, excludeFirst);
}
};
// Driver code
int main() {
vector<int> nums = {2, 3, 2};
Solution obj;
cout << obj.rob(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of houses, because the two linear ranges are processed once and each house is handled a constant number of times.

Space Complexity: O(1), because only a fixed number of variables are used while processing each linear range.

Interview follow-up Questions

The first and last houses are adjacent. Any valid answer must exclude at least one endpoint, so comparing the range without the last house and the range without the first house covers every legal choice.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0