🌟 Beats 100.00% 👏  ||  Easy and Step-by-Step Breakdown 💯🔥
\n\n## \uD83C\uDF1F Access Daily LeetCode Solutions Repo : click here\n\n---\n\n\n\n---\n\n# Intuition\nWhen I first saw this problem, I noticed that the goal i
![github_promotion_dark.png](https://assets.leetcode.com/users/images/51ebd525-2680-47bf-9734-dd61a5dd210b_1731639415.0025911.png)\n\n## **\uD83C\uDF1F Access Daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/b5a51b8d-9d24-4e36-b029-c79c2ff7a7d1_1731639381.1025076.png)\n\n---\n\n# Intuition\nWhen I first saw this problem, I noticed that the goal is to make the array sorted by removing the shortest possible subarray. This means:\n1. We should look for any parts of the array that are already sorted and try to retain as much of that as possible.\n2. If we have a long sorted prefix (from the start) and a long sorted suffix (from the end), we might only need to remove a small subarray in between to make the entire array sorted.\n\nBy focusing on these already sorted sections, we can potentially minimize the length of the subarray that needs to be removed.\n\n---\n\n# Approach\nHere\u2019s the approach I used to solve this problem efficiently:\n\n1. **Find the longest non-decreasing prefix** from the beginning of the array. Let\'s call this `left`. This gives us the starting part of the array that\u2019s already sorted.\n\n2. **Find the longest non-decreasing suffix** from the end of the array. Let\'s call this `right`. This gives us the ending part of the array that\u2019s already sorted.\n\n3. **Check if the entire array is sorted** by verifying if `left` spans the whole array. If so, the answer is `0` because we don\'t need to remove anything.\n\n4. **Calculate minimum removal**:\n   - Initially, consider removing either the entire suffix (`n - left - 1` elements) or the entire prefix (`right` elements).\n   - Use a two-pointer technique to see if we can merge parts of the prefix and suffix by skipping the smallest possible middle section. This allows us to explore shorter subarrays to remove.\n\n5. **Return the result** which is the minimum number of elements we need to remove.\n\n---\n\n# Complexity\n- **Time complexity**: \\(O(n)\\), since we\u2019re only scanning the array a few times (once for the prefix, once for the suffix, and once for merging with two pointers).\n- **Space complexity**: \\(O(1)\\), as we\u2019re only using a few extra variables for indices and result calculation.\n\n---\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        \n        // Step 1: Find the longest non-decreasing prefix\n        int left = 0;\n        while (left + 1 < n && arr[left] <= arr[left + 1]) {\n            left++;\n        }\n        \n        // If the entire array is already sorted\n        if (left == n - 1) return 0;\n        \n        // Step 2: Find the longest non-decreasing suffix\n        int right = n - 1;\n        while (right > 0 && arr[right - 1] <= arr[right]) {\n            right--;\n        }\n        \n        // Step 3: Find the minimum length to remove by comparing prefix and suffix\n        int result = min(n - left - 1, right);\n        \n        // Step 4: Use two pointers to find the smallest middle part to remove\n        int i = 0, j = right;\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                result = min(result, j - i - 1);\n                i++;\n            } else {\n                j++;\n            }\n        }\n        \n        return result;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int findLengthOfShortestSubarray(int[] arr) {\n        int n = arr.length;\n        \n        // Step 1: Find the longest non-decreasing prefix\n        int left = 0;\n        while (left + 1 < n && arr[left] <= arr[left + 1]) {\n            left++;\n        }\n        \n        // If the entire array is already sorted\n        if (left == n - 1) return 0;\n        \n        // Step 2: Find the longest non-decreasing suffix\n        int right = n - 1;\n        while (right > 0 && arr[right - 1] <= arr[right]) {\n            right--;\n        }\n        \n        // Step 3: Find the minimum length to remove by comparing prefix and suffix\n        int result = Math.min(n - left - 1, right);\n        \n        // Step 4: Use two pointers to find the smallest middle part to remove\n        int i = 0, j = right;\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                result = Math.min(result, j - i - 1);\n                i++;\n            } else {\n                j++;\n            }\n        }\n        \n        return result;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[]} arr\n * @return {number}\n */\nvar findLengthOfShortestSubarray = function(arr) {\n    const n = arr.length;\n    \n    // Step 1: Find the longest non-decreasing prefix\n    let left = 0;\n    while (left + 1 < n && arr[left] <= arr[left + 1]) {\n        left++;\n    }\n    \n    // If the entire array is already sorted\n    if (left === n - 1) return 0;\n    \n    // Step 2: Find the longest non-decreasing suffix\n    let right = n - 1;\n    while (right > 0 && arr[right - 1] <= arr[right]) {\n        right--;\n    }\n    \n    // Step 3: Find the minimum length to remove by comparing prefix and suffix\n    let result = Math.min(n - left - 1, right);\n    \n    // Step 4: Use two pointers to find the smallest middle part to remove\n    let i = 0, j = right;\n    while (i <= left && j < n) {\n        if (arr[i] <= arr[j]) {\n            result = Math.min(result, j - i - 1);\n            i++;\n        } else {\n            j++;\n        }\n    }\n    \n    return result;\n};\n\n```\n```Python []\nclass Solution:\n    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n        n = len(arr)\n        \n        # Step 1: Find the longest non-decreasing prefix\n        left = 0\n        while left + 1 < n and arr[left] <= arr[left + 1]:\n            left += 1\n        \n        # If the entire array is already sorted\n        if left == n - 1:\n            return 0\n        \n        # Step 2: Find the longest non-decreasing suffix\n        right = n - 1\n        while right > 0 and arr[right - 1] <= arr[right]:\n            right -= 1\n        \n        # Step 3: Find the minimum length to remove by comparing prefix and suffix\n        result = min(n - left - 1, right)\n        \n        # Step 4: Use two pointers to find the smallest middle part to remove\n        i, j = 0, right\n        while i <= left and j < n:\n            if arr[i] <= arr[j]:\n                result = min(result, j - i - 1)\n                i += 1\n            else:\n                j += 1\n        \n        return result\n\n```\n```Go []\nfunc findLengthOfShortestSubarray(arr []int) int {\n    n := len(arr)\n    \n    // Step 1: Find the longest non-decreasing prefix\n    left := 0\n    for left+1 < n && arr[left] <= arr[left+1] {\n        left++\n    }\n    \n    // If the entire array is already sorted\n    if left == n-1 {\n        return 0\n    }\n    \n    // Step 2: Find the longest non-decreasing suffix\n    right := n - 1\n    for right > 0 && arr[right-1] <= arr[right] {\n        right--\n    }\n    \n    // Step 3: Find the minimum length to remove by comparing prefix and suffix\n    result := min(n-left-1, right)\n    \n    // Step 4: Use two pointers to find the smallest middle part to remove\n    i, j := 0, right\n    for i <= left && j < n {\n        if arr[i] <= arr[j] {\n            result = min(result, j-i-1)\n            i++\n        } else {\n            j++\n        }\n    }\n    \n    return result\n}\n\nfunc min(a, b int) int {\n    if a < b {\n        return a\n    }\n    return b\n}\n\n```\n\n---\n\n# Step-by-Step Detailed Explanation\n\nEach step involves identifying portions of the array that are already sorted and strategically merging them to minimize the middle section that needs removal. This two-pointer technique ensures we find the optimal solution efficiently.\n\n---\n\n![upvote_cat.png](https://assets.leetcode.com/users/images/42f1ee71-9509-4bb0-984a-b600c2064f6e_1731639697.3579538.png)\n
['Array', 'Two Pointers', 'Binary Search', 'Stack', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']