✅ 3 Method ||C++ || Beginner Friendly ||Beat 100%
\n\n### 1. Brute Force Approach\nThe brute force approach tries all possible subarrays that can be removed and checks if the remaining array is non-decreasing.\
\n\n### 1. **Brute Force Approach**\nThe brute force approach tries all possible subarrays that can be removed and checks if the remaining array is non-decreasing.\n\n#### Steps:\n1. Iterate through all possible subarray start and end indices \\([l, r]\\).\n2. Check if the array becomes non-decreasing after removing the subarray.\n3. Track the shortest subarray to remove.\n\n#### Code:\n```cpp\n\nclass Solution {\npublic:\n    bool isNonDecreasing(vector<int>& arr, int l, int r) {\n        int n = arr.size();\n        for (int i = 0; i < n - 1; ++i) {\n            if (i >= l && i < r) continue;\n            int nextIdx = (i + 1 == l) ? r : i + 1;\n            if (nextIdx < n && arr[i] > arr[nextIdx]) return false;\n        }\n        return true;\n    }\n\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        int minLength = n;  // Worst case: remove the entire array\n\n        for (int l = 0; l < n; ++l) {\n            for (int r = l; r < n; ++r) {\n                if (isNonDecreasing(arr, l, r)) {\n                    minLength = min(minLength, r - l);\n                }\n            }\n        }\n\n        return minLength;\n    }\n};\n```\n\n#### Complexity:\n- **Time Complexity**: \\(O(n^3)\\)  \n  - Two loops for all subarrays \\([l, r]\\): \\(O(n^2)\\).\n  - For each subarray, check non-decreasing: \\(O(n)\\).\n- **Space Complexity**: \\(O(1)\\).\n\n---\n\n### 2. **Optimized Two-Pointer Approach**\nThis approach takes advantage of the fact that the array is already sorted in parts. We find the longest sorted prefix and suffix and compute the minimum removal needed.\n\n#### Steps:\n**The logic aims to find the shortest subarray to remove to make the entire array non-decreasing by leveraging the existing non-decreasing prefix and suffix.\n\n1. **Identify Prefix and Suffix**: Find the longest non-decreasing prefix (`i`) and suffix (`j`). If the whole array is non-decreasing, return 0.\n\n2. **Initial Result**: Calculate the length to remove if only the middle section between prefix and suffix is removed (`min(n - i - 1, j)`).\n\n3. **Two-Pointer Merge**: Use two pointers, `left` (starting from the beginning of the prefix) and `right` (starting at the suffix). \n   - If `arr[left] <= arr[right]`, update `result` with the length between `left` and `right` (the subarray to remove) and increment `left`.\n   - If not, increment `right`.\n\n4. **Return Result**: The minimum result from these steps gives the shortest removable subarray length.**\n\n#### Code:\n```cpp\n\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        int left = 0, right = n - 1;\n\n        // Find the longest non-decreasing prefix\n        while (left + 1 < n && arr[left] <= arr[left + 1]) ++left;\n\n        // If the entire array is sorted\n        if (left == n - 1) return 0;\n\n        // Find the longest non-decreasing suffix\n        while (right > 0 && arr[right - 1] <= arr[right]) --right;\n\n        // Initial assumption: remove everything between the prefix and suffix\n        int minLength = min(n - left - 1, right);\n\n        // Try merging prefix and suffix\n        int i = 0, j = right;\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                minLength = min(minLength, j - i - 1);\n                ++i;\n            } else {\n                ++j;\n            }\n        }\n\n        return minLength;\n    }\n};\n```\n\n#### Complexity:\n- **Time Complexity**: \\(O(n)\\)  \n  - Prefix and suffix identification: \\(O(n)\\).\n  - Two-pointer merge: \\(O(n)\\).\n- **Space Complexity**: \\(O(1)\\).\n\n---\n\n### 3. **Binary Search Approach**\nInstead of using two pointers to merge prefix and suffix, we can use binary search to find the rightmost index in the suffix that can merge with a given prefix.\n\n#### Steps:\n1. Identify the longest non-decreasing prefix (`left`) and suffix (`right`).\n2. For each index in the prefix, use binary search to find the smallest valid index in the suffix that can merge with it.\n3. Track the shortest subarray to remove.\n\n#### Code:\n```cpp\n\n\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        int left = 0, right = n - 1;\n\n        // Find the longest non-decreasing prefix\n        while (left + 1 < n && arr[left] <= arr[left + 1]) ++left;\n\n        // If the entire array is sorted\n        if (left == n - 1) return 0;\n\n        // Find the longest non-decreasing suffix\n        while (right > 0 && arr[right - 1] <= arr[right]) --right;\n\n        // Initial assumption: remove everything between the prefix and suffix\n        int minLength = min(n - left - 1, right);\n\n        // Use binary search to merge prefix and suffix\n        for (int i = 0; i <= left; ++i) {\n            int j = lower_bound(arr.begin() + right, arr.end(), arr[i]) - arr.begin();\n            minLength = min(minLength, j - i - 1);\n        }\n\n        return minLength;\n    }\n};\n```\n\n#### Complexity:\n- **Time Complexity**: \\(O(n log n)\\)  \n  - Prefix and suffix identification: \\(O(n)\\).\n  - Binary search for each prefix element: \\(O(log n)\\), repeated up to \\(O(n)\\).\n- **Space Complexity**: \\(O(1)\\).\n\n---\n
['Array', 'Two Pointers', 'Binary Search', 'C++']