remove n consecutive elements from array, so that amplitude of remaining elements is minimal

Question

Given array A, I need to remove K consecutive elements, so that the amplitude(difference between maximal and minimal elements) of the remaining elements will be minimal. e.g A=[3,5,1,3,9,8], K=4, the answer should be 1. I could remove [3,5,1,3] to get 1.

I saw a similar post here: Program to find minimal amplitude after removing consecutive elements from array, someone commented about using prefix and suffix minimum and maximum, but I do not know what it means and how that would be helpful. If anybody could clarify/provide other suggestions that would be great.

Answer 1

O(n) solution with prefix/suffix minima/maxima:

def solution(A, K):
    pre = zip(acc(A, min, initial=inf),
              acc(A, max, initial=-inf))
    suf = list(zip(list(acc(A[::-1], min, initial=inf))[::-1],
                    list(acc(A[::-1], max, initial=-inf))[::-1]))
    return min(max(left[1], right[1]) - min(left[0], right[0])
               for left, right in zip(pre, suf[K:]))

For your example A = [3,5,1,3,9,8] we have the prefix minima/maxima and suffix minima/maxima:

pre: (∞,-∞) (3,3) (3,5) (1,5) (1,5) (1,9) (1,9)
suf:  (1,9) (1,9) (1,9) (3,9) (8,9) (8,8) (∞,-∞)

After aligning for K = 4 you have:

pre:                         (∞,-∞) (3,3) (3,5) (1,5) (1,5) (1,9) (1,9)
suf:  (1,9) (1,9) (1,9) (3,9) (8,9) (8,8) (∞,-∞)

For example the pairing of left = (3,5) and right = (∞,-∞) corresponds to a left subarray [3,5] and right subarray [] after removing [1,3,9,8]. Where the minimum of left and right side is min(3,∞)=3 and the maximum is max(5,-∞)=5, for an amplitude of 5-3=2.

Ten random tests against naive brute force reference solution:

917 917 True
908 908 True
898 898 True
925 925 True
939 939 True
954 954 True
905 905 True
899 899 True
927 927 True
934 934 True

Whole code (Try it online!):

from itertools import accumulate as acc
from math import inf
from random import choices

def solution(A, K):
    pre = zip(acc(A, min, initial=inf),
              acc(A, max, initial=-inf))
    suf = list(zip(list(acc(A[::-1], min, initial=inf))[::-1],
                    list(acc(A[::-1], max, initial=-inf))[::-1]))
    return min(max(left[1], right[1]) - min(left[0], right[0])
               for left, right in zip(pre, suf[K:]))

print(solution([3, 5, 1, 3, 9, 8], 4))

def naive(A, K):
    result = inf
    for i in range(len(A) + 1 - K):
        copy = A.copy()
        del copy[i : i+K]
        result = min(result, max(copy) - min(copy))
    return result

print(naive([3, 5, 1, 3, 9, 8], 4))

for _ in range(10):
    A = choices(range(1000), k=100)
    K = 50
    expect = naive(A, K)
    result = solution(A, K)
    print(expect, result, result == expect)