note1574.md

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

• Type: Two pointers
• Approach:
  • Find the right most j such that arr[j – 1] > arr[j], if not found which means the entire array is sorted return 0. Then we have a non-descending subarray arr[j~n-1].
  • We maintain two pointers i, j, such that arr[0i] is non-descending and arr[i] <= arr[j] which means we can remove arr[i+1j-1] to get a non-descending array. Number of elements to remove is j – i – 1.
• Complexity:
  • Time: O(n)
  • Space: O(1)