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

Problem statement

https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/

Solution

Find longest not-decreasing prefix and suffix.
For each element from suffix use binary search to find where we can start prefix.

Complexity

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

Code

class Solution:
    def findLengthOfShortestSubarray(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   

Remark

Once we found the biggest prefix and suffix, we can use two pointers/sliding window approach to get O(n) total time complexity, similar to merge sort.