Longest Well Performing Interval - Leetcode Solution

The Longest Well-Performing Interval problem on LeetCode is a problem that requires you to find the length of the longest contiguous subarray (interval) in an array of integers, such that the sum of the subarray is greater than or equal to zero.

To solve this problem, you can use a prefix sum array to maintain the sum up to each index in the array. Then you can iterate through the prefix sum array and keep track of the minimum prefix sum seen so far. If the current prefix sum minus the minimum prefix sum is greater than zero, then the sum of the subarray starting with the minimum prefix sum and ending with the current prefix sum is greater than or equal to zero. You can then update the length of the longest subarray seen so far.

Here is the detailed solution in Python:

def longestWPI(hours: List[int]) -> int:
    prefix_sum = [0] * (len(hours) + 1)
    for i in range(1, len(hours) + 1):
        if hours[i-1] > 8:
            prefix_sum[i] = prefix_sum[i-1] + 1
        else:
            prefix_sum[i] = prefix_sum[i-1] - 1
    
    stack = []
    for i, val in enumerate(prefix_sum):
        if not stack or val < prefix_sum[stack[-1]]:
            stack.append(i)
    
    ans = 0
    i = len(prefix_sum) - 1
    while i > ans:
        while stack and prefix_sum[i] > prefix_sum[stack[-1]]:
            ans = max(ans, i - stack.pop())
        i -= 1
    
    return ans

In this solution, we first create a prefix sum array that stores the cumulative sum up to each index. Then we iterate through the prefix sum array and use a stack to keep track of the indices where the prefix sum is strictly increasing. We do this because we want to find the longest subarray where the sum is positive, so we only need to consider subarrays that start at these increasing indices.

Once we have the stack of increasing indices, we iterate through the prefix sum array in reverse order and pop indices from the stack if the current prefix sum is greater than the prefix sum corresponding to the index at the top of the stack. We do this because we want to find the longest subarray that ends at the current index where the sum is positive, so we only need to consider subarrays that end at these decreasing indices.

As we're popping indices from the stack, we update the answer variable with the difference between the current index and the popped index if the resulting subarray is longer than the previous longest subarray seen so far. We continue this process until we have processed all indices in the prefix sum array.

In the end, we return the length of the longest subarray seen so far as our answer.

1