loading

House Robber II — Step-by-Step Visualization

mediumLeetCode #213ArrayDynamic Programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Algorithm Pattern

Dynamic Programming (Circular Constraint)

Key Idea

Since the houses are in a circle, we cannot rob both the first and the last house simultaneously. This circular problem can be reduced to two linear 'House Robber I' sub-problems: 1. Rob houses from index `0` to `n-2` (exclude the last house). 2. Rob houses from index `1` to `n-1` (exclude the first house). The final answer is the maximum of these two results. Note: For a single house, the answer is just that house's value.

Step-by-Step Approach

  1. If `len(nums) == 1`, return `nums[0]`.
  2. Define a helper function `rob_linear(arr)` to solve the standard House Robber I problem.
  3. Calculate `res1 = rob_linear(nums[:-1])`.
  4. Calculate `res2 = rob_linear(nums[1:])`.
  5. Return `max(res1, res2)`.

Common Gotchas

  • Don't forget the base case for 1 house.
  • The two linear sub-problems handle the circular dependency by ensuring the 'neighbors-at-the-end' are never picked together.

Related Problems

← All problems