#213

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

House Robber II

Maximize your loot by robbing houses arranged in a circle without alerting the police using dynamic programming.

Problem Statement

You are a professional robber planning to rob houses along a street. The houses are arranged in a circle, meaning the first house is adjacent to the last one. Adjacent houses are connected to a security system that contacts the police if broken into on the same night. Given an array nums representing the amount of money in each house, determine the maximum money you can rob without triggering any alarms.

Since the first and last houses are adjacent, they cannot be robbed together. Therefore, the solution requires maximizing loot from either the subarray excluding the first house or excluding the last house, which makes this a state transition dynamic programming problem.

Examples

Example 1

Input: nums = [2,3,2]

Output: 3

You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2

Input: nums = [1,2,3,1]

Output: 4

Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example 3

Input: nums = [1,2,3]

Output: 3

Example details omitted.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Solution Approach

Divide the Problem into Two Subarrays

Since the first and last houses are adjacent, they cannot both be robbed. The problem is split into two subproblems: one where the first house is excluded, and another where the last house is excluded. This reduces the problem to two linear subproblems.

Apply Dynamic Programming to Each Subproblem

For both subarrays, we use dynamic programming to decide at each house whether to rob it or skip it. This ensures that we consider the maximum loot without triggering alarms between adjacent houses.

Combine Results

After solving the two subproblems, the final result is the maximum loot from either subarray, which represents the optimal solution to the problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to the two passes over the array to compute the maximum loot for each subproblem. Space complexity is O(1) if we use optimized space for dynamic programming, or O(n) if we store results for each house.

What Interviewers Usually Probe

The candidate identifies the need to handle the circular nature of the problem.
They break the problem into two linear subproblems, using dynamic programming in each case.
The candidate demonstrates the ability to optimize space usage in dynamic programming solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the circular nature of the problem, leading to incorrect assumptions about which houses can be robbed together.
Not optimizing space usage in dynamic programming, leading to unnecessary memory consumption.
Misunderstanding the subproblem breakdown and incorrectly applying dynamic programming to the entire array without separating the two cases.

Follow-up variants

Allowing multiple rounds of robbery, where you can rob houses again after a set number of nights.
Adding additional constraints, such as limits on the number of houses you can rob in one go.
Robbing houses with variable amounts of money that change each night.

FAQ

How can I solve the House Robber II problem efficiently?

The solution requires breaking the problem into two subarrays, excluding either the first or the last house, and applying dynamic programming to each subarray.

Why can't I rob both the first and last house in House Robber II?

Since the houses are arranged in a circle, the first and last houses are adjacent. Robbing both would trigger the security system, so they must be considered separately.

What is the time complexity of the optimal solution for House Robber II?

The optimal solution has a time complexity of O(n), as we make two passes over the array to solve each subproblem.

What type of dynamic programming is used in House Robber II?

This problem uses state transition dynamic programming to decide at each house whether to rob it or skip it.

Can you optimize the space complexity for House Robber II?

Yes, by storing only the previous two results in dynamic programming, the space complexity can be reduced to O(1).

terminal

Solution

Solution 1: Dynamic Programming

The circular arrangement means that at most one of the first and last houses can be chosen for theft, so this circular arrangement problem can be reduced to two single-row house problems.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def rob(self, nums: List[int]) -> int:
        def _rob(nums):
            f = g = 0
            for x in nums:
                f, g = max(f, g), f + x
            return max(f, g)

        if len(nums) == 1:
            return nums[0]
        return max(_rob(nums[1:]), _rob(nums[:-1]))

Continue Practicing

#221 maximal square #198 house robber #188 best time to buy and sell stock iv