Problem statement

https://leetcode.com/problems/longest-well-performing-interval/

Solution

Let us replace all numbers which are > 8 with 1 and all others with -1. Then what we need to find is the longest positive window. Notice that either we need to find window with sum equal to 1 or we have any prefix with sum > 0. For each value we can keep the smallest index where cumulative sum equal to this value. Then we check if we have value - 1 previousy and if we have, update answer.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def longestWPI(self, H):
        arr = [int(x > 8)*2 - 1 for x in H]
        acc = [0] + list(accumulate(arr))
        d, ans = {}, 0
        for i, x in enumerate(acc):
            if x > 0: ans = max(i, ans)
            if x - 1 in d:
                ans = max(ans, i - d[x - 1])
            if x not in d:
                d[x] = i
                
        return ans

Solution 2

There is more universal solution with monotonic stack. Idea is to evaluate prefix sums again, then put them to strictly monotone decreasing stack. Finally we traverse prefix sums in the opposite direction and pop elements from stack until we can.

Complexity

It is O(n) for time and space, but now it works for any input. Also it can easily be modified to find the longest subarray with sum >= K.

Code

class Solution:
    def longestWPI(self, H):
        arr = [int(x > 8)*2 - 1 for x in H]
        n = len(arr)
        acc = [0] + list(accumulate(arr))
        
        stack, res = [], 0
        for i in range(n + 1):
            if not stack or acc[stack[-1]] > acc[i]:
                stack += [i]
                
        for j in range(n, -1, -1):
            while stack and acc[stack[-1]] + 0 < acc[j]:
                res = max(res, j - stack.pop())
                
        return res