0 ms || Beat 100% || With Explanation
Intuition\n- The idea is to find the shortest subarray that needs to be removed to make the entire array sorted. We can do this by first finding the first eleme
# Intuition\n- **The idea is to find the shortest subarray that needs to be removed to make the entire array sorted. We can do this by first finding the first element from the left that is out of order, and the first element from the right that is out of order. If the entire array is already sorted, we can return 0.\n**\n\n---\n\n- Next, we find the minimum and maximum values in the unsorted subarray. We then extend the unsorted subarray to include any elements that are out of order. Finally, we return the length of the unsorted subarray, or 0 if the entire array is already sorted.\n\n\n![5834d094-01ae-4508-8795-0703cee8e5b8_1711243639.7934008 (1).png](https://assets.leetcode.com/users/images/1ab10c0e-f0ae-4de8-b577-ffb994200abf_1731650936.481465.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Step 1: Find the first element from the left that is out of order\nIntuition: We want to find the first element that breaks the increasing order from the left. This will help us identify the start of the unsorted subarray.\n\n1. Step 2: Check if the array is already sorted\nIntuition: If the entire array is already sorted, we can return 0 as no subarray needs to be removed.\n\n1. Step 3: Find the first element from the right that is out of order\nIntuition: We want to find the first element that breaks the increasing order from the right. This will help us identify the end of the unsorted subarray.\n\n1. Step 4: Find the minimum and maximum values in the unsorted subarray\nIntuition: We need to know the range of values in the unsorted subarray to determine which elements need to be included.\n1.  Step 5: Return the length of the shortest subarray that needs to be removed\nIntuition: The length of the shortest subarray is the difference between the length of the entire array and the length of the longest subarray that can be kept\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: The time complexity of this solution is O(n), where n is the size of the input array.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity of this solution is O(1), as we only use a constant amount of extra space to store the left and right pointers, and the minimum and maximum values.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#include <vector>  \n#include <algorithm>  \n\nclass Solution {  \npublic:  \n    int findLengthOfShortestSubarray(std::vector<int>& arr) {  \n        int n = arr.size();  \n        int left = 0;  \n        int right = n - 1;  \n\n        // Find the first element from the left that is out of order  \n        while (left + 1 < n && arr[left] <= arr[left + 1]) {  \n            left++;  \n        }  \n\n        // If the array is already sorted, return 0  \n        if (left == n - 1) {  \n            return 0;  \n        }  \n\n        // Find the first element from the right that is out of order  \n        while (right - 1 >= left && arr[right] >= arr[right - 1]) {  \n            right--;  \n        }  \n\n        int ans = std::max(n - right, left + 1);  \n        int i = 0, j = right;  \n        while (i <= left && j < n) {  \n            if (arr[i] <= arr[j]) {  \n                ans = std::max(ans, i + 1 + (n - j));  \n                i++;  \n            } else {  \n                j++;  \n            }  \n        }  \n\n        return n - ans;  \n    }  \n};\n```\n```java []\nimport java.util.Arrays;  \n\nclass Solution {  \n    public int findLengthOfShortestSubarray(int[] arr) {  \n        int n = arr.length;  \n        int left = 0;  \n        int right = n - 1;  \n\n        // Find the first element from the left that is out of order  \n        while (left + 1 < n && arr[left] <= arr[left + 1]) {  \n            left++;  \n        }  \n\n        // If the array is already sorted, return 0  \n        if (left == n - 1) {  \n            return 0;  \n        }  \n\n        // Find the first element from the right that is out of order  \n        while (right - 1 >= left && arr[right] >= arr[right - 1]) {  \n            right--;  \n        }  \n\n        int ans = Math.max(n - right, left + 1);  \n        int i = 0, j = right;  \n        while (i <= left && j < n) {  \n            if (arr[i] <= arr[j]) {  \n                ans = Math.max(ans, i + 1 + (n - j));  \n                i++;  \n            } else {  \n                j++;  \n            }  \n        }  \n\n        return n - ans;  \n    }  \n}\n```\n```python []\nclass Solution:  \n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:  \n        n = len(arr)  \n        left = 0  \n        right = n - 1  \n\n        # Find the first element from the left that is out of order  \n        while left + 1 < n and arr[left] <= arr[left + 1]:  \n            left += 1  \n\n        # If the array is already sorted, return 0  \n        if left == n - 1:  \n            return 0  \n\n        # Find the first element from the right that is out of order  \n        while right - 1 >= left and arr[right] >= arr[right - 1]:  \n            right -= 1  \n\n        ans = max(n - right, left + 1)  \n        i, j = 0, right  \n        while i <= left and j < n:  \n            if arr[i] <= arr[j]:  \n                ans = max(ans, i + 1 + (n - j))  \n                i += 1  \n            else:  \n                j += 1  \n\n        return n - ans\n```\n```C []\n#include <stdio.h>  \n#include <stdlib.h>  \n#include <math.h>  \n\nint findLengthOfShortestSubarray(int* arr, int arrSize) {  \n    int left = 0;  \n    int right = arrSize - 1;  \n\n    // Find the first element from the left that is out of order  \n    while (left + 1 < arrSize && arr[left] <= arr[left + 1]) {  \n        left++;  \n    }  \n\n    // If the array is already sorted, return 0  \n    if (left == arrSize - 1) {  \n        return 0;  \n    }  \n\n    // Find the first element from the right that is out of order  \n    while (right - 1 >= left && arr[right] >= arr[right - 1]) {  \n        right--;  \n    }  \n\n    int ans = fmax(arrSize - right, left + 1);  \n    int i = 0, j = right;  \n    while (i <= left && j < arrSize) {  \n        if (arr[i] <= arr[j]) {  \n            ans = fmax(ans, i + 1 + (arrSize - j));  \n            i++;  \n        } else {  \n            j++;  \n        }  \n    }  \n\n    return arrSize - ans;  \n}  \n\n\n```\n\n\n
['Binary Search', 'C', 'Python', 'C++', 'Java']