How do you solve House Robber II on LeetCode?

House Robber II (LeetCode #213) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The circular arrangement of houses introduces a constraint that can be handled by breaking the problem into two linear cases.

What is the brute force solution for House Robber II?

The brute force approach for House Robber II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves trying all possible combinations of houses to rob, ensuring that no two adjacent houses are robbed. This is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve House Robber II?

House Robber II uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Array.

What are the interview tips for House Robber II?

Always clarify the constraints of the problem, especially with circular or linear arrangements. Think about how you can break the problem into smaller parts that are easier to solve. Practice dynamic programming problems to become familiar with recognizing patterns.

What are common mistakes when solving House Robber II?

Students often forget to handle the circular nature of the problem, leading to incorrect results. Failing to recognize that the problem can be broken down into simpler subproblems.

#213

House Robber II

Medium

ArrayDynamic ProgrammingDynamic ProgrammingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages dynamic programming to break the problem into smaller subproblems. Since the houses are in a circle, we can solve the problem by considering two cases: robbing from the first house to the second last house or from the second house to the last house.

⚙️

Algorithm

3 steps

1Step 1: Define a helper function to calculate the maximum money that can be robbed in a linear arrangement of houses.
2Step 2: Call this helper function twice: once excluding the last house and once excluding the first house.
3Step 3: Return the maximum of the two results.

solution.py13 lines

1# Full working Python code
2
3def rob(nums):
4    if len(nums) == 1:
5        return nums[0]
6    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
7
8
9def rob_linear(houses):
10    prev, curr = 0, 0
11    for money in houses:
12        prev, curr = curr, max(prev + money, curr)
13    return curr

ℹ

Complexity note: The time complexity is O(n) because we only traverse the list of houses a couple of times. The space complexity is O(1) since we are using a constant amount of space for variables.

1The circular arrangement of houses introduces a constraint that can be handled by breaking the problem into two linear cases.
2Dynamic programming is effective for optimizing problems with overlapping subproblems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.