Sliding Window Approach
Brute Force Approach\nRemove every possible subarray and check whether the remaining array is in sorted order. The solution exceeds the time limit.\n\nclass Sol
**Brute Force Approach**\nRemove every possible subarray and check whether the remaining array is in sorted order. The solution exceeds the time limit.\n```\nclass Solution:\n\tdef findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n\t\tn = len(arr)\n\t\tans = float("inf")\n\t\tfor i in range(n):\n\t\t\tfor j in range(i, n+1):\n\t\t\t\tif self.issorted(arr[:i] + arr[j:]):\n\t\t\t\t\tans = min(ans, j - i)\n\t\treturn ans\n\t\tdef issorted(self, arr):\n\t\t\tl = len(arr)\n\t\t\tfor i in range(1, l):\n\t\t\t\tif arr[i] < arr[i-1]:\n\t\t\t\t\treturn False\n\t\treturn True\n```\nTime Complexity : O(n^3)\n\n**Sliding Window**\nFrom left to right, check the longest possible subarray starting at index 0 which is in non decreasing order. This subarray ends at p1. If p1 is the end of the array(p1 = n - 1), the entire array is in non decreasing order and we do not have to delete any subarray. So answer will be zero in this case. Otherwise we have to remove the elements from p1 to n.\n\nLet us use this array to visualise the operation: 1 2 3 4 3 2 3 4 5 3 2 3 4 5 6\nGreen elements remain and the red ones have to be deleted.\nAfter the first operation, p1 = 3.\n![image](https://assets.leetcode.com/users/images/fbc02736-d3c9-4d03-bdb5-fc93768fa5f6_1616208462.5387356.png)\n\nNow from right to left, check the longest possible non decreasing array starting at index p2 (initially p2 = n-1) and ending at the last element. From p2 to n, the array is in sorted order. Remove the subarray from 0 to p2-1.\nAfter second operation, p2 = 10\n![image](https://assets.leetcode.com/users/images/1e6f5107-11ca-4ee5-80e8-aa54c263dea8_1616208533.829657.png)\nThe required number of elements to be removed is minimum of n \u2013 p1 \u2013 1 and p2.\nans = min(n \u2013 p1 \u2013 1, p2)\n\nAs we can see, in the sequence,\n![image](https://assets.leetcode.com/users/images/ed0ff71f-fb31-4860-b6aa-23b690017de9_1616208588.0631073.png)\nwe do not need to remove the entire left subarray, we can keep the elements from position 0 to 1(1,2) so that the sequence remains in sorted as shown below.\n![image](https://assets.leetcode.com/users/images/6c8c3bd1-e8ec-45e6-ba3e-c75181e40598_1616208633.9820664.png)\n\nTo find this we use the sliding window approach. Let the left and right pointers of the window be 0 and p2 initially. We have to remove certain elements between left and right.\n\nWe do the following till left pointer <= p1 and right pointer < n:\n\tCase 1 : If arr[left] <= arr[right] we can keep the element at left in the array, so we increment left pointer.\n\tCase 2: Else we cannot keep the element at left pointer, so we increment right pointer to make the sequence increasing.\n\tans = min(ans, right \u2013 left)\n\t\n![image](https://assets.leetcode.com/users/images/001e9ec9-41ce-4016-9b52-db0677eadec7_1616208872.123042.png)\n\n```\nclass Solution:\n\tdef findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n\t\tn = len(arr)\n\t\tans = float("inf")\n\t\tp1 = 0\n\t\twhile p1 < n - 1 and arr[p1] <= arr[p1 + 1]:\n\t\t\tp1 += 1\n\t\t# no need to remove anything\n\t\tif p1 == n - 1:\n\t\t\treturn 0\n\t\tp2 = n - 1\n\t\twhile p2 > 0 and arr[p2] >= arr[p2-1]:\n\t\t\tp2 -= 1\n\t\tans = min(n - p1 - 1, p2)\n\t\t#sliding window\n\t\tleft = 0\n\t\tright = p2\n\t\twhile left <= p1 and right < n:\n\t\t\tif arr[left] <= arr[right]:\n\t\t\t\tleft += 1\n\t\t\telse:\n\t\t\t\tright += 1\n\t\t\tans = min(ans, right - left)\nreturn ans\n```\n\nTime Complexity :\nWe visit each element not more than 3 times.\nTherefore complexity = O(3*n) = O(n)\nSpace Complexity : O(1)\nConstant extra space is used.\n\n\n\n
[]