C# Solution for Shortest Subarray to be Removed to Make Array Sorted Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to make the array non-decreasing by removing the shortest possi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to make the array non-decreasing by removing the shortest possible subarray. This means identifying the segments of the array that are already in non-decreasing order and seeing if we can make the array non-decreasing by removing only the smallest part of the array between these segments.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tIdentify Longest Non-Decreasing Segments:\n\t\u2022\tLeft Segment: Starting from the beginning, find the longest segment that is already non-decreasing. The end of this segment is marked by the variable left.\n\t\u2022\tRight Segment: Starting from the end, find the longest segment that is non-decreasing and mark its start with the variable right.\n2.\tHandle Edge Case - Already Sorted Array:\n\t\u2022\tIf left and right cover the entire array (i.e., left reaches the end of the array), then the array is already sorted, and we can return 0.\n3.\tCalculate Minimum Removals:\n\t\u2022\tInitially, calculate the number of elements to remove by removing either everything after left or everything before right.\n4.\tOptimize by Merging Segments:\n\t\u2022\tUse a two-pointer technique to try merging the left and right segments. For each valid pair of indices (i, j) where arr[i] <= arr[j], compute the length of the subarray that would need to be removed (i.e., elements between i and j), and update the minimum removal length accordingly.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\t\u2022\tFinding the left and right segments takes O(n).\n\t\u2022\tThe two-pointer merge approach also takes O(n) since each pointer moves at most n times across the array.\n\t\u2022\tThus, the total time complexity is O(n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n\t\u2022\tThe solution only uses a constant amount of extra space (e.g., left, right, i, j, minRemoval), so the space complexity is O(1).\n\n# Code\n```csharp []\npublic class Solution {\n    public int FindLengthOfShortestSubarray(int[] arr) {\n        int n = arr.Length;\n        int left = 0;\n        while (left + 1 < n && arr[left] <= arr[left + 1]) {\n            left++;\n        }\n        if (left == n - 1) {\n            return 0;\n        }\n        int right = n - 1;\n        while (right > 0 && arr[right - 1] <= arr[right]) {\n            right--;\n        }\n        int minRemoval = Math.Min(n - left - 1, right); \n        int i = 0;\n        int j = right;\n        while (i <= left && j < n) {\n            if (arr[i] <= arr[j]) {\n                minRemoval = Math.Min(minRemoval, j - i - 1);\n                i++;\n            } else {\n                j++;\n            }\n        }\n        \n        return minRemoval;\n    }\n}\n```
['C#']