Longest Well-Performing Interval

A more efficient solution uses the concept of prefix sums combined with a HashMap. As before, we convert tiring days to +1 and non-tiring days to -1. We then compute the prefix sum as we iterate through this new score array.

The problem is to find indices i and j (i <= j) that maximize j - i + 1, such that the sum of scores from i to j is positive. This sum can be expressed as prefixSum[j] - prefixSum[i-1] > 0, or prefixSum[j] > prefixSum[i-1].

We can iterate through the array with index j, calculating the current_sum (which is prefixSum[j]). For each j, we need to find the earliest index i-1 where the prefix sum was smaller than current_sum. A HashMap is used to store the first index at which each prefix sum value appeared. This allows us to find the required i-1 efficiently.

1. Transform the problem: represent tiring days as +1 and non-tiring days as -1. The goal is to find the longest subarray with a sum > 0.
2. This problem can be solved in a single pass using a HashMap and the concept of prefix sums.
3. Initialize sum = 0, maxLength = 0, and a HashMap map to store the first-seen index of each prefix sum. Add a base case map.put(0, -1) to handle intervals starting from index 0.
4. Iterate through the hours array from i = 0 to n-1: a. Update the running sum: sum += (hours[i] > 8) ? 1 : -1. b. If sum is not already in the map, store its first occurrence: map.put(sum, i). c. Check if the current prefix sum sum is positive. If sum > 0, it means the interval from the beginning [0, i] is well-performing. Its length is i + 1. Update maxLength = max(maxLength, i + 1). d. If sum <= 0, we look for a previous prefix sum prev_sum such that sum - prev_sum > 0, which simplifies to prev_sum < sum. To get the longest such interval ending at i, we need the earliest (smallest index) prev_sum. The best candidate for this is sum - 1, as it represents the smallest possible positive difference (1). We check if map.containsKey(sum - 1). If it exists, it means we found an interval [map.get(sum - 1) + 1, i] with a sum of 1. We update maxLength = max(maxLength, i - map.get(sum - 1)).
5. Return maxLength.

We iterate through the array once, maintaining a running sum. We use a HashMap to keep track of the first time we encounter each sum value. The key is the sum, and the value is the index.

We initialize the map with {0: -1} to correctly handle cases where a well-performing interval starts at index 0.

For each day i, we update our sum.

• If sum > 0, the entire interval from the start [0, i] is well-performing. This has length i+1, which is the longest possible interval ending at i. We update our max length accordingly.
• If sum <= 0, a well-performing interval ending at i must start at some k > 0. We are looking for a previous prefix sum, prev_sum, that is less than the current sum. To maximize the interval length i - k, we need the smallest k. The condition sum - prev_sum > 0 is equivalent to prev_sum <= sum - 1. The key insight is that we only need to check for the existence of sum - 1 in our map. If map.containsKey(sum - 1), we have found an interval with a sum of at least 1, and map.get(sum - 1) gives us the end index of the prefix that we subtract. The length of this interval is i - map.get(sum - 1). We update our max length with this value if it's larger.

We only add a sum to the map if it's not already there. This ensures we always have the earliest index for any given sum, which is crucial for finding the longest interval.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestWPI(int[] hours) {
        int maxLength = 0;
        int sum = 0;
        // Map to store the first occurrence of a prefix sum
        Map<Integer, Integer> map = new HashMap<>();
        // Base case for intervals starting at index 0
        map.put(0, -1);

        for (int i = 0; i < hours.length; i++) {
            sum += (hours[i] > 8) ? 1 : -1;

            // If the current sum is positive, the interval from the beginning is well-performing.
            // This is the longest possible interval ending at i.
            if (sum > 0) {
                maxLength = i + 1;
            } else {
                // If sum <= 0, we look for a previous prefix sum `sum - 1`.
                // This guarantees an interval sum of `sum - (sum - 1) = 1 > 0`.
                // We check for `sum - 1` because it gives the longest possible interval
                // for a subarray ending at `i` with a positive sum.
                if (map.containsKey(sum - 1)) {
                    maxLength = Math.max(maxLength, i - map.get(sum - 1));
                }
            }
            
            // Store the first time we see a particular sum.
            // If the sum is already in the map, we don't update it because we want the earliest index.
            map.putIfAbsent(sum, i);
        }

        return maxLength;
    }
}