Lesson

14.5House Robber Circular House

Problem Statement

You are a professional robber planning to rob houses along a street. All houses at this place are arranged in a circle, meaning the first house is the neighbor of the last one. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected. 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.

Example 1

Input: nums = [2,3,2]
Output: 3
Explanation:
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
Explanation:
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
Explanation:
Rob house 1 (money = 1) and rob house 3 (money = 3).

Constraints

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

Approach

Brute Force (Recursive)

Steps:

Understand the Problem:
- Houses are arranged in a circle; the first and last houses are adjacent.
- You cannot rob two adjacent houses.
- Aim to maximize the total amount of money robbed.
Identify Choices:
- For each house, decide whether to rob it or not.
- Due to the circular arrangement, robbing the first house means you cannot rob the last house, and vice versa.
Recursive Exploration:
- Implement two scenarios:
  - Scenario 1: Rob the first house and exclude the last house.
  - Scenario 2: Exclude the first house and consider robbing the last house.
- For each scenario, use a helper recursive function to decide whether to rob each house.
Base Cases:
- If there are no houses left (index >= nums.length), return 0.
- If there is only one house left, return its value.
Implementation:
- Implement a recursive function that explores both choices (rob or not rob) for each house within the defined scenarios.
- Calculate the maximum amount from both scenarios and return the higher value.

Time & Space Complexity:

Time Complexity: O(2ⁿ)
Each house has two choices (rob or not rob), leading to an exponential number of possibilities.
Space Complexity: O(n)
The recursion stack can go as deep as the number of houses.

Code Snippet:

Dry Run:

Let's perform a dry run for nums = [1, 2, 3, 1].

Scenario 1: Rob first house (index 0) and exclude last house (index 3).

Scenario 2: Exclude first house (index 0) and consider robbing last house (index 3).

Final Calculation:

So, the maximum amount of money you can rob is 4.

b. Optimized Approach (Dynamic Programming - Memoization)

Steps:

Understand the Problem:
- Same as brute force, but aim to optimize by avoiding redundant calculations.
Identify Overlapping Subproblems:
- The recursive calls for the same indices are repeated in the brute force approach.
Memoization:
- Use a memo object to store the results of subproblems.
- Before computing the result for an index, check if it's already in the memo.
Handle Circular Constraint:
- Similar to the brute force approach, consider two scenarios:
  - Scenario 1: Rob the first house and exclude the last house.
  - Scenario 2: Exclude the first house and consider robbing the last house.
Implementation:
- Implement a helper function with memoization for each scenario.
- Return the maximum result from both scenarios.

Time & Space Complexity:

Time Complexity: O(n)
Each house's result is computed once and stored in the memo, eliminating redundant calculations.
Space Complexity: O(n)
The memo object stores results for each house, and the recursion stack can go as deep as the number of houses.

Code Snippet:

Dry Run:

Let's perform a dry run for nums = [2, 7, 9, 3, 1].

Scenario 1: Rob first house (index 0) and exclude last house (index 4).

Scenario 2: Exclude first house (index 0) and consider robbing last house (index 4).

Final Calculation:

So, the maximum amount of money you can rob is 11.

Complexity Analysis

Brute Force Time & Space:
- Time Complexity: O(2ⁿ)
  The recursive solution explores all possible combinations of robbing or not robbing each house, leading to an exponential number of function calls.
- Space Complexity: O(n)
  The recursion stack can go as deep as the number of houses, requiring linear space.
Optimized Time & Space (Memoization):
- Time Complexity: O(n)
  Each house's maximum rob amount is computed once and stored in the memo, eliminating redundant calculations.
- Space Complexity: O(n)
  The memo object stores the result for each house, and the recursion stack can still go as deep as the number of houses.

Conclusion

When tackling problems like the House Robber II, where houses are arranged in a circle, it's essential to choose the right approach to ensure efficiency and correctness.

Brute Force (Recursive):
- Pros:
  - Simple and easy to implement.
  - Good for understanding the problem's fundamental structure.
- Cons:
  - Highly inefficient for larger inputs due to its exponential time complexity.
  - Redundant calculations make it impractical for real-world scenarios.
Optimized Approach (Dynamic Programming - Memoization):
- Pros:
  - Significantly reduces time complexity by storing and reusing results of subproblems.
  - Efficient and scalable for larger inputs.
- Cons:
  - Requires additional space for the memoization storage.
  - Slightly more complex to implement compared to the brute force method.

Key Takeaways:

Brute Force methods are straightforward and useful for small input sizes or as a starting point to understand the problem.
Dynamic Programming (Memoization) enhances the brute force approach by eliminating redundant computations, making it suitable for larger and more complex problems.
Circular Constraints:
- In problems where the input has a circular arrangement (like houses in a circle), consider breaking it down into scenarios that exclude specific elements to handle the circular dependency.
Always assess whether a problem has an optimal substructure and overlapping subproblems, which are indicators that Dynamic Programming can be effectively applied.
Choosing the right problem-solving technique not only improves the efficiency of your solution but also demonstrates a deeper understanding of algorithmic principles, which is crucial for programming and technical interviews.

Previous Next