Beats 100% | Optimal Code | Longest Increasing SubArray
Intuition\nTo make the array sorted, we want to remove as few elements as possible. Instead of trying to find every possible subarray we could remove, we can si
# Intuition\nTo make the array sorted, we want to remove as few elements as possible. Instead of trying to find every possible subarray we could remove, we can simplify the problem by focusing on two naturally sorted sections of the array: a sorted prefix (starting from the beginning) and a sorted suffix (starting from the end).\n\nThe key insight here is:\n\nIf we remove elements between a sorted prefix and a sorted suffix, we can potentially leave a large part of the array sorted, requiring minimal removals.\n\n# Approach\nTo solve this problem efficiently and without extra space, we need to focus on two main parts of the array: a prefix that\u2019s already sorted and a suffix that\u2019s already sorted. By examining these two parts, we can find the minimal subarray that disturbs the sorted order and remove it.\n\nSolution Steps:\n\n1. Find the Longest Sorted Prefix: Start from the beginning of the array and move forward until the order breaks. This part of the array (prefix) is already sorted. You can always store using extra space, but optimally you should avoid it.\n\n2. Find the Longest Sorted Suffix: Start from the end of the array and move backward until the order breaks. This part (suffix) is also sorted.\n\n3. Evaluate the Removal Lengths:\ni) If the prefix length or suffix length covers the whole array, it\u2019s already sorted, and the answer is 0.\nii) The minimum length of the subarray to be removed will be either:\n   -> The elements between the end of prefix and the start of suffix.\n   -> The overlap between the end of prefix and the start of suffix where prefix values are less than or equal to suffix values.\n\n4. Combine Prefix and Suffix: Use two pointers, one at the end of prefix and the other at the start of suffix, and try to "connect" them without breaking the order. Adjust these pointers to minimize the subarray length.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```cpp []\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 sorted prefix\n        while (left + 1 < n && arr[left] <= arr[left + 1]) {\n            left++;\n        }\n        if (left == n - 1) return 0;  // Entire array is sorted\n        \n        // Find the longest sorted suffix\n        while (right > 0 && arr[right - 1] <= arr[right]) {\n            right--;\n        }\n        \n        // Calculate minimum removal length\n        int minLen = min(n - left - 1, right); // Remove middle portion\n        int i = 0, j = right;\n        \n        // Try to connect prefix and suffix\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                minLen = min(minLen, j - i - 1);\n                i++;\n            } else {\n                j++;\n            }\n        }\n        return minLen;\n    }\n};\n\n```
['C++']