(1) Two Pointers (Optimized), (2) Binary Search with Explanations
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTwo Pointers. \n\n# Complexity\n- Time complexity: O(n)\n Add your time c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTwo Pointers. \n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n = len(arr)\n\n        # 1. set pointers to the head and tail\n        lo, hi = 0, n - 1\n\n        # 2. find the longest ascending array on the left side\n        # increasing pattern in [0, ..., lo]\n        while lo < n - 1 and arr[lo] <= arr[lo + 1]:\n            lo += 1\n\n        # 3. find the longest ascending array on the right side\n        # increasing pattern in [hi, ..., n - 1]\n        while hi > 0 and arr[hi - 1] <= arr[hi]:\n            hi -= 1\n\n        # stop \n        if lo >= hi:\n            return 0\n\n        # 4. initial solution; either left or right subarray\n        # left side size := lo + 1\n        # right side size := n - hi\n        # number of remove := n - size of each array\n        res = min(n - (lo + 1), hi)\n\n        # 5. improve solution by merging arr[0, ...,lo] with arr[hi,.., n-1]\n        i = 0        # pointer to travers arr[0, ...,lo]\n        j = hi       # pointer to travers arr[hi,.., n-1]\n\n        while i <= lo and j < n:\n            # arr[0, .., i] can be merged with arr[j,.., n - 1]\n            # delete arr[i + 1,.., j] with size j - (i + 1)\n            if arr[i] <= arr[j]:\n                res = min(res, j - (i + 1))\n                i += 1\n            # check the next j then\n            else:\n                j += 1\n\n        return res\n```\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nBinary Search. \n\n# Complexity\n- Time complexity: O(n * log n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        def findIndex(nums, lo, hi, target):\n            while lo <= hi:\n                mid = (lo + hi) // 2\n                if nums[mid] < target:\n                    lo = mid + 1\n                else:\n                    hi = mid - 1\n            return lo\n\n        n = len(arr)\n        # 1. set pointers to the head and tail\n        lo, hi = 0, n - 1\n\n        # 2. find the longest ascending array on the left side\n        # increasing pattern in [0, ..., lo]\n        while lo < n - 1 and arr[lo] <= arr[lo + 1]:\n            lo += 1\n\n        # 3. find the longest ascending array on the right side\n        # increasing pattern in [hi, ..., n - 1]\n        while hi > 0 and arr[hi - 1] <= arr[hi]:\n            hi -= 1\n\n        # stop \n        if lo >= hi:\n            return 0\n\n        # 4. initial solution; either left or right subarray\n        # left side size := lo + 1\n        # right side size := n - hi\n        # number of remove := n - size of each array\n        res = min(n - (lo + 1), hi)\n\n        # 5. improve solution by merging arr[0, ...,lo] with arr[hi,.., n-1]\n        # for each val in left sub-array arr[0, ...,lo], \n        # find and index in right sub-array where arr[i] <= arr[j]\n        for i in range(lo + 1):\n            target = arr[i]\n\n            # run binary search to find left most index in arr[hi,.., n-1]\n            j = findIndex(arr, hi, n - 1, target)\n\n            # arr[0, .., i] can be merged with arr[j,.., n - 1]\n            # delete arr[i + 1,.., j] with size j - (i + 1)\n            res = min(res, j - (i + 1))\n\n        return res\n```
['Array', 'Two Pointers', 'Binary Search', 'Stack', 'Monotonic Stack', 'Python3']