House Robber II

House Robber II

What is this problem about?

The House Robber II interview question is a direct sequel to the original House Robber problem. The premise is the same: you want to maximize your loot from houses along a street without robbing adjacent ones. However, there is a major twist: the street is a circle. This means the first house and the last house are now adjacent, and robbing both will trigger the alarm.

Why is this asked in interviews?

Companies like Meta, Amazon, and Uber use this problem to see if a candidate can adapt a known solution to a new constraint. It evaluations your ability to handle circular dependencies in Dynamic Programming. The challenge lies in breaking the circle into linear components, demonstrating that you can simplify complex structures into manageable sub-problems.

Algorithmic pattern used

This problem uses the Linear DP pattern from the first House Robber problem, applied twice. Since you cannot rob both the first and the last house, the solution must be the maximum of two scenarios:

1. Robbing houses from the first to the second-to-last (ignoring the last house).
2. Robbing houses from the second to the last (ignoring the first house). By running the standard $O(n)$ House Robber algorithm on these two sub-arrays, you effectively cover all valid possibilities.

Example explanation

Houses: [2, 3, 2]

1. Scenario 1 (Ignore last): [2, 3]. Standard House Robber result = 3.
2. Scenario 2 (Ignore first): [3, 2]. Standard House Robber result = 3. Max of both is 3. (Note: if it were linear, you could get 4 by robbing the two 2s).

Houses: [1, 2, 3, 1]

1. Scenario 1 (1 to 3): [1, 2, 3]. Result = 4.
2. Scenario 2 (2 to 4): [2, 3, 1]. Result = 4. Max result: 4.

Common mistakes candidates make

• Not Handling small arrays: Failing to handle cases where there is only 1 house (simply return its value).
• Overlapping Logic: Trying to solve the circle in a single DP pass, which is significantly more complex than the "two-linear-passes" approach.
• Complexity: Re-implementing the DP logic twice instead of creating a helper function.

Interview preparation tip

Always look for ways to "break" circularity. Most circular array or string problems can be solved by either concatenating the array to itself or, as in this case, running a linear algorithm on two different segments.