Stickler Thief II

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Circular house robber: houses arranged in circle so first and last are adjacent. Run linear robber twice.

Algorithm

1Case 1: rob houses 0..n-2. Case 2: rob houses 1..n-1. Answer = max of both cases.

Common Pitfalls

•Same as LC 213. Cannot rob both first and last. Solve two linear sub-problems.

Stickler Thief II.java

Java

// Approach: Circular array DP. Run house robber DP twice: once excluding first, once excluding last; take max.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    int maxValue(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);

        for (int i = 2; i < n - 1; i++)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);

        int ans1 = dp[n - 2];
        Arrays.fill(dp, 0);
        dp[1] = arr[1];
        for (int i = 2; i < n; i++)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);

        int ans2 = dp[n - 1];
        return Math.max(ans1, ans2);
    }
}

Was this solution helpful?