DSA problem
House Robber II
You are a professional robber planning to rob houses along a street. This time the houses are arranged in a circle: that is, the first house is the neighbor of the last one. Adjacent houses still have connected security systems, so robbing two of them on the same night triggers the alarm. Given an integer array nums representing the money in each house, return the maximum amount of money you can rob without alerting the police.
The circular arrangement adds a single extra constraint over House Robber I: houses 0 and n - 1 are now adjacent, so they can't both be robbed. Every other rule and every other piece of intuition carries over unchanged.
The clean reduction is to split the problem into two linear sub-problems and take the better outcome. Either the robber skips house n - 1 and considers nums[0 .. n - 2], or the robber skips house 0 and considers nums[1 .. n - 1]. The first scenario removes the circular conflict involving the last house, the second removes it for the first house, and any valid circular plan falls into one of the two — never both at once.
For each linear sub-array we apply the standard House Robber I bottom-up DP with two rolling variables: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]). The final answer is the maximum of the two sub-solutions, computed in O(n) time and O(1) extra space.
Examples
nums = [2,3,2]3nums = [1,2,3,1]4nums = [1,2,3]3Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
- The houses are arranged in a circle; the first and last houses are adjacent.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.