Problem statement

https://binarysearch.com/problems/Remove-Smallest-Peaks-in-Order/

Solution

We need to simulate the process. Because we extract elements from the middle, we need to keep structure like double linked list. Also we keep in heap values (A[i], i).

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, A):
        def add_heap(cur):
            if cur == -1: return
            tprv, tnxt = prv[cur], nxt[cur]
            if A[tprv] < A[cur] > A[tnxt]:
                heappush(heap, (A[cur], cur))

        n = len(A)
        if n in [0, 1]: return A
        A += [-inf]
        res, heap = [], []
        prv, nxt = {}, {}

        for i in range(n):
            prv[i] = i-1
            nxt[i] = i+1
        nxt[n-1] = -1

        for i in range(n): add_heap(i)
        
        while heap:
            val, i = heappop(heap)
            res += [val]
            prv[nxt[i]] = prv[i]
            nxt[prv[i]] = nxt[i]
            for cur in prv[i], nxt[i]:
                add_heap(cur)

        return res