Problem statement

https://binarysearch.com/problems/Minimize-Amplitude-After-Deleting-K-Length-Sublist/

Solution

Evalutae cumulative min and max of prefixes and suffixes.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A, k):
        PINF, MINF = float("inf"), -float("inf")
        pref_min = [PINF] + list(accumulate(A, min))
        pref_max = [MINF] + list(accumulate(A, max))
        suff_min = list(accumulate(A[::-1], min))[::-1] + [PINF] 
        suff_max = list(accumulate(A[::-1], max))[::-1] + [MINF]
        n = len(A)
        ans = PINF
        for i in range(n - k + 1):
            mn = min(pref_min[i], suff_min[i + k])
            mx = max(pref_max[i], suff_max[i + k])
            ans = min(ans, mx - mn)
        return ans