[Python] Binary Search + Merge Sorting with thought process when being asked on interviews
Binary Search\nLet\'s observe the problem first, which asks us to remove ONE subarray to make the array non-decreasing. This is very important because it tells 
### Binary Search\nLet\'s observe the problem first, which asks us to remove *ONE* subarray to make the array non-decreasing. This is very important because it tells us where to look at for the approach. \nThe subarray to remove could be starting from the first element, or just ending at the last element.  Both are simple cases, we can just iterate each `num` to extend the non-decreasing subarray until the condition is not satisfied, then the rest of numbers are removed. \n\nThe difficult part is for the third case, where the subarray starts and ends in the middle. Then how can we find where the subarray starts and ends?\nSince the array is non-decreasing after removing the subarray, then we can guarantee both the left and right side to the removed subarray is non-decreasing. So we still can reuse the results we done for the simple cases, called `left` and `right` respecitvely. \n\nThe next work is to merge the two parts. But how? In order to merge 2 pieces, we need find the greatest number in `left` that is smaller than some number in the `right`. Since both are sorted, then we can find the index of greatest number in `left` for each num in `right` using binary search. Then select the shortest subarray to remove.\n\n```python\ndef findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n\tn = len(arr)\n    i, j = 0, n - 1\n    while i + 1 < n and arr[i + 1] >= arr[i]:\n\t\ti += 1\n\twhile j - 1 >= 0 and arr[j - 1] <= arr[j]:\n\t\tj -= 1\n\tif i >= j:\n\t\treturn 0\n\treturn min(*[k - bisect.bisect(arr[:i + 1], arr[k]) for k in range(j, n)], n - i - 1, j)\n```\n\nThis approach resovles in *O(NlgN)* time complexity, and it passed the tests. However, it seems slow, can we improve it?\n\n### Merge Sorting\nLet\'s observe more the binary search apporach. We didn\'t make use of the property that the `right` is sorted also. What does it mean? \nIt indicates that for any number `b` in `right` that appears after `a`, the index we searched out from `left` for `b` must be larger than the one we found for `a` since `right` is sorted.\nSo with this observation, we don\'t need run binary search multiple times, we can just linear search for the next valid number in `left` from where we left off for pervious number in `right`. \nFor example, we have `[3, 5]` as `right`, `[1,3,4,5]` as `left`, and the index we got for `3` in `right` is `1` in `left`, then we can continue searching `[4, 5]` in `left` for `5` in `right`. Then `3` is found.\nRight, we can just simulate the merge sorting to increase the header of piece that is smaller and get the length of merged subarray until either runs out of elements.\n\n```python\ndef findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n\tn = len(arr)\n    i, j = 0, n - 1\n    while i + 1 < n and arr[i + 1] >= arr[i]:\n\t\ti += 1\n\twhile j - 1 >= 0 and arr[j - 1] <= arr[j]:\n\t\tj -= 1\n\tif i >= j:\n\t\treturn 0\n\tshortest = min(n - i - 1, j)\n    k = 0\n    while k <= i and j < n:\n\t\tif arr[k] <= arr[j]:\n\t\t\tshortest = min(shortest, j - k - 1)\n\t\t\tk += 1\n        else:\n            j += 1\n\treturn shortest\n```\n\n*Time Complexity*= **O(N)**\n*Space Complexity*= **O(1)**\n\n
[]