[C++] Binary Search + DP
Basic Idea - \n- Make a prefix and suffix array of longest continuous non decreasing and non increasing subarrays of the given array.\n- Now, apply Binary Searc
Basic Idea - \n- Make a prefix and suffix array of longest continuous non decreasing and non increasing subarrays of the given array.\n- Now, apply Binary Search on the size of window to be removed.\n\t- Lowest : 0\n\t- Highest : `n-1` (`n` = size of given array)\n- Now simulate the removal of windows of `size=mid` and if the `remaining left elements + remaining right elements == n-size` and `a[left-1] <= a[right+1]` then this size of window can be removed (see `ok` function)\n- If the ok function returns true, do `high = mid` else `low = mid+1`.\n \n\nTime Complexity : `O(n log n)`\nSpace Complexity : `O(n)`\n\n```\n// itne me hi thakk gaye?\nclass Solution {\npublic:\n    bool ok(int &size, vector<int> &pref, vector<int> &suff, vector<int> &arr, int &n) {\n        for(int start=0; start<=n-size; start++) {\n            int end = start + size - 1;\n            int left = (start <= 0) ? 0 : pref[start-1];\n            int right = (end >= n-1) ? 0 : suff[end+1];\n            int le = (start <= 0) ? -1e9+2 : arr[start-1];\n            int re = (end >= n-1) ? 1e9+2 : arr[end+1];\n            if (left + right == n-size && le <= re) {\n                return true;\n            }\n        }\n        return false;\n    }\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        if (!n || n==1) return 0;\n        vector<int> pref(n, 1);\n        vector<int> suff(n, 1);\n        for(int i=1; i<n; i++) {\n            if (arr[i] >= arr[i-1]) pref[i] = pref[i-1]+1;\n        }\n        for(int i=n-2; i>=0; i--) {\n            if (arr[i] <= arr[i+1]) suff[i] = suff[i+1]+1;\n        }\n        int low = 0;\n        int high = n-1;\n        while(low < high) {\n            int mid = (low + high)/2;\n            if(ok(mid, pref, suff, arr, n)) high = mid;\n            else low = mid+1;\n            if(high - low == 1) break;\n        }\n        if (ok(low, pref, suff, arr, n)) return low;\n        return high;\n    } \n};\n```
['Dynamic Programming', 'C', 'Binary Tree']