Problem statement

https://binarysearch.com/problems/Shortest-Sublist-to-Remove-to-Make-Sorted-List/

Solution

Equal to Leetcode 1574. Shortest Subarray to be Removed to Make Array Sorted.

Complexity

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

Code

class Solution:
    def solve(self, A):
        if A == sorted(A): return 0
        n = len(A)
        pref, i = [A[0]], 0
        while A[i + 1] >= A[i]:
            pref += [A[i + 1]]
            i += 1
        
        suff, i = [A[-1]], n - 1
        while A[i - 1] <= A[i]:
            suff += [A[i - 1]]
            i -= 1
            
        ans = len(pref)  
        for i, x in enumerate(suff):
            ans = max(ans, i + bisect.bisect(pref, x) + 1)     
        return n - ans