C++ O(N) Sliding window; Explanation with Illustrations
See my latest update in repo LeetCode\n\n\n----\n\n# Solution 1.\n\nScan from left to right, find the first index left that A[left] > A[left + 1].\n\nIf left ==
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n\n----\n\n# Solution 1.\n\nScan from left to right, find the first index `left` that `A[left] > A[left + 1]`.\n\nIf `left == N - 1`, this array is already non-descending, return `0`.\n\nScan from right to left, find the first index `right` that `A[right] < A[right - 1]`.\n\n![image](https://assets.leetcode.com/users/images/83d5a46b-1785-4682-8f65-706fd25017cc_1599384728.703493.png)\n\n\nNow we loosely have two options, either deleting the left-side `right` nodes, or deleting the right-side `N - left - 1` nodes.\n![image](https://assets.leetcode.com/users/images/ffa7aae1-9e33-4749-85db-9fd91f313dca_1599384738.062273.png)\n\n![image](https://assets.leetcode.com/users/images/6063c0e4-9136-48e6-b6a5-7407fb538845_1599384745.1044443.png)\n\n\nSo the answer is at most `min(N - left - 1, right)`.\n\nNow we can use a sliding window / two pointers to get tighter result.\n\nLet `i = 0, j = right`. And we examine if we can delete elements between `i` and `j` (exclusive) by comparing `A[i]` and `A[j]`.\n\n![image](https://assets.leetcode.com/users/images/859141be-738d-4a0c-979f-899b5ceb9766_1599384968.365021.png)\n\n\n\n**Case 1:** `A[j] >= A[i]`, we can delete elements inbetween, so we can try to update the answer using `j - i - 1` and increment `i` to tighten the window.\n\n![image](https://assets.leetcode.com/users/images/c90e526e-ea2a-4c78-a791-8ddda8048c60_1599384760.5704896.png)\n\n\n**Case 2:** `A[j] < A[i]`, we can\'t delete elements inbetween, so we increment `j` to loosen the window.\n\n![image](https://assets.leetcode.com/users/images/1f717bbb-1009-4f05-b463-f7a0d60c7ef9_1599384769.8815608.png)\n\n\nWe loop until `i > left` or `j == N`. And the answer we get should be the minimal possible solution.\n\n```cpp\n// OJ: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\n// Ref: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/830416/Java-Increasing-From-Left-Right-and-Merge-O(n)\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& A) {\n        int N = A.size(), left = 0, right = N - 1;\n        while (left + 1 < N && A[left] <= A[left + 1]) ++left;\n        if (left == A.size() - 1) return 0;\n        while (right > left && A[right - 1] <= A[right]) --right;\n        int ans = min(N - left - 1, right), i = 0, j = right;\n        while (i <= left && j < N) {\n            if (A[j] >= A[i]) {\n                ans = min(ans, j - i - 1);\n                ++i;\n            } else ++j;\n        }\n        return ans;\n    }\n};\n```\n\n---\n# Original Approach (Incorrect)\n**Oops, sorry my original approach below is incorrect because it can\'t pass `[1,2,3,10,0,7,8,9]`. :(**\n## Case 1\n\n![image](https://assets.leetcode.com/users/images/add08aaa-158c-4581-92b7-30d0080419d6_1599322591.4854705.png)\n\n\nWe scan from left to right and stop at the first "bad" node where `A[i] < A[i -1]`. Now we have an option to delete all the nodes from `A[i]` to `A[j]` where `A[j]` is the first node from the end that is either smaller than `A[i - 1]` or `A[j] > A[j + 1]`.\n\n## Case 2\n\n![image](https://assets.leetcode.com/users/images/8292c620-9803-4903-a01f-f8c982a24ba7_1599322630.6638007.png)\n\nWe scan from right to left and stop at the first "bad" node where `A[i] > A[i + 1]`. Now we have an option to delete all the nodes from `A[i]` to `A[j]` where `A[j]` is the first node from the beginning that is either greater than `A[i + 1]` or `A[j] < A[j - 1]`.\n\n\n```cpp\n// OJ: https://leetcode.com/contest/biweekly-contest-34/problems/shortest-subarray-to-be-removed-to-make-array-sorted/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\n// NOTE: this solution is INCORRECT. It can\'t pass [1,2,3,10,0,7,8,9]. I left this here just for people who landed on the same wrong idea.\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& A) {\n        int N = A.size(), ans = N - 1, i;\n        for (i = 1; i < N; ++i) {\n            if (A[i] >= A[i - 1]) continue;\n            int j = N - 1;\n            while (j > i && A[j] >= A[i - 1] && (j == N - 1 || A[j] <= A[j + 1])) --j;\n            ans = min(ans, j - i + 1);\n            break;\n        }\n        if (i == N) return 0;\n        for (i = N - 2; i >= 0; --i) {\n            if (A[i] <= A[i + 1]) continue;\n            int j = 0;\n            while (j < i && A[j] <= A[i + 1] && (j == 0 || A[j] >= A[j - 1])) ++j;\n            ans = min(ans, i - j + 1);\n            break;\n        }\n        return ans;\n    }\n};\n```
[]