101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming with Two Cases - Complex approach
  2. Space-Optimized Dynamic Programming - Complex approach

Approach 1: Dynamic Programming with Two Cases

The key insight for solving this problem is to recognize that it's a variation of the House Robber problem with a circular arrangement.

In the original House Robber problem, we use dynamic programming to find the maximum amount of money we can rob without alerting the police. The recurrence relation is:

dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

where dp[i] represents the maximum amount of money we can rob from the first i houses.

However, in this problem, the houses are arranged in a circle, which means the first and last houses are adjacent. This creates a constraint: we can't rob both the first and last houses.

To handle this constraint, we can consider two separate cases:

  1. Rob houses from index 0 to n-2 (excluding the last house)
  2. Rob houses from index 1 to n-1 (excluding the first house)

For each case, we can apply the original House Robber algorithm. The final answer is the maximum of these two cases.

This approach works because by excluding either the first or last house, we break the circular arrangement and can apply the original algorithm.

Algorithm:

  1. If the array has only one element, return that element.
  2. If the array has only two elements, return the maximum of the two.
  3. For arrays with three or more elements, consider two cases:
  4. a. Rob houses from index 0 to n-2 (excluding the last house):
  5. i. Initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
  6. ii. For i from 2 to n-2, dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
  7. iii. The maximum amount for this case is dp[n-2].
  8. b. Rob houses from index 1 to n-1 (excluding the first house):
  9. i. Initialize dp[0] = nums[1] and dp[1] = max(nums[1], nums[2]).
  10. ii. For i from 2 to n-2, dp[i] = max(dp[i-1], dp[i-2] + nums[i+1]).
  11. iii. The maximum amount for this case is dp[n-2].
  12. Return the maximum of the two cases.

Time Complexity:

O(n)

Where n is the number of houses. We need to iterate through the array twice, once for each case.

Space Complexity:

O(n)

We use an array of size n to store the dynamic programming values for each case.

Approach 2: Space-Optimized Dynamic Programming

We can optimize the space complexity of the previous approach by observing that to calculate dp[i], we only need the values of dp[i-1] and dp[i-2].

Instead of using an array to store all the dp values, we can use two variables to keep track of the previous two values.

This reduces the space complexity from O(n) to O(1).

Algorithm:

  1. If the array has only one element, return that element.
  2. If the array has only two elements, return the maximum of the two.
  3. For arrays with three or more elements, consider two cases:
  4. a. Rob houses from index 0 to n-2 (excluding the last house):
  5. i. Initialize prev2 = nums[0] and prev1 = max(nums[0], nums[1]).
  6. ii. For i from 2 to n-2, current = max(prev1, prev2 + nums[i]), then update prev2 = prev1 and prev1 = current.
  7. iii. The maximum amount for this case is prev1.
  8. b. Rob houses from index 1 to n-1 (excluding the first house):
  9. i. Initialize prev2 = nums[1] and prev1 = max(nums[1], nums[2]).
  10. ii. For i from 2 to n-2, current = max(prev1, prev2 + nums[i+1]), then update prev2 = prev1 and prev1 = current.
  11. iii. The maximum amount for this case is prev1.
  12. Return the maximum of the two cases.

Time Complexity:

O(n)

Where n is the number of houses. We need to iterate through the array twice, once for each case.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function rob(nums):
    n = length of nums
 
    if n == 1:
        return nums[0]
    if n == 2:
        return max(nums[0], nums[1])
 
    // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
    dp1 = new array of size n-1
    dp1[0] = nums[0]
    dp1[1] = max(nums[0], nums[1])
 
    for i from 2 to n-2:
        dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i])
 
    // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
    dp2 = new array of size n-1
    dp2[0] = nums[1]
    dp2[1] = max(nums[1], nums[2])
 
    for i from 2 to n-2:
        dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i+1])
 
    return max(dp1[n-2], dp2[n-2])
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone