[ C++ | Java | Kotlin ] Simple binary search solution, detailed explanation, 0 ms, beats 100% 🚀
Intuition\nThe key insight is that after removing a subarray to make the remaining elements non-decreasing, the result will consist of two parts:\n1. A non-decr
# Intuition\nThe key insight is that after removing a subarray to make the remaining elements non-decreasing, the result will consist of two parts:\n1. A non-decreasing prefix from the left\n2. A non-decreasing suffix from the right\n\nThe optimal solution must use some (or all) elements from either/both of these parts. We can find these parts and then use binary search to find the shortest subarray to remove that connects them properly.\n\n# Approach\nThe solution works in three main steps:\n\n1. **Find the longest non-decreasing prefix:**\n```kotlin\nvar increaseLeftIndex = 0\nwhile (increaseLeftIndex + 1 < arr.size && arr[increaseLeftIndex] <= arr[increaseLeftIndex + 1]) {\n    increaseLeftIndex++\n}\n```\nThis finds the longest sequence from the left that\'s already in non-decreasing order.\n\n2. **Find the longest non-decreasing suffix:**\n```kotlin\nvar decreaseRightIndex = n - 1\nwhile (decreaseRightIndex - 1 >= 0 && arr[decreaseRightIndex - 1] <= arr[decreaseRightIndex]) {\n    decreaseRightIndex--\n}\n```\nThis finds the longest sequence from the right that\'s already in non-decreasing order.\n\n3. **Binary search for the shortest removable subarray:**\n- The `check(value)` function verifies if we can make the array non-decreasing by removing a subarray of length `value`\n- For each possible starting position `i`, it checks if removing `value` elements starting at position `i` creates a valid solution\n- A valid solution must:\n  - Start within the left non-decreasing sequence (`i - 1 <= increaseLeftIndex`)\n  - End within the right non-decreasing sequence (`i + value >= decreaseRightIndex`)\n  - Maintain non-decreasing order at the connection point (`arr[i - 1] <= arr[i + value]`)\n\nThe binary search efficiently finds the minimum length of the subarray we need to remove to satisfy these conditions.\n\n# Complexity\nTime Complexity: $$O(n * log(n))$$, where `n` is the length of the array\nSpace Complexity: $$O(log(n))$$ for stack in binary search\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findLengthOfShortestSubarray(vector<int>& arr) {\n        int n = arr.size();\n        int increaseLeftIndex = 0;\n        while (increaseLeftIndex + 1 < arr.size() && arr[increaseLeftIndex] <= arr[increaseLeftIndex + 1]) {\n            increaseLeftIndex++;\n        }\n        \n        int decreaseRightIndex = n - 1;\n        while (decreaseRightIndex - 1 >= 0 && arr[decreaseRightIndex - 1] <= arr[decreaseRightIndex]) {\n            decreaseRightIndex--;\n        }\n        \n        return binSearch(0, n, increaseLeftIndex, decreaseRightIndex, arr);\n    }\n    \nprivate:\n    bool check(int value, int increaseLeftIndex, int decreaseRightIndex, const vector<int>& arr) {\n        int n = arr.size();\n        for (int i = 0; i <= n - value; i++) {\n            if (i - 1 <= increaseLeftIndex && i + value >= decreaseRightIndex &&\n                (i == 0 || i + value == n || arr[i - 1] <= arr[i + value])\n            ) {\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    int binSearch(int left, int right, int increaseLeftIndex, int decreaseRightIndex, const vector<int>& arr) {\n        if (left >= right) return right;\n        int mid = left + (right - left) / 2;\n        return check(mid, increaseLeftIndex, decreaseRightIndex, arr) ?\n                    binSearch(left, mid, increaseLeftIndex, decreaseRightIndex, arr) :\n                    binSearch(mid + 1, right, increaseLeftIndex, decreaseRightIndex, arr);\n    }\n};\n```\n```java []\nclass Solution {\n    public int findLengthOfShortestSubarray(int[] arr) {\n        int n = arr.length;\n        int increaseLeftIndex = 0;\n        while (increaseLeftIndex + 1 < arr.length && arr[increaseLeftIndex] <= arr[increaseLeftIndex + 1]) {\n            increaseLeftIndex++;\n        }\n        \n        int decreaseRightIndex = n - 1;\n        while (decreaseRightIndex - 1 >= 0 && arr[decreaseRightIndex - 1] <= arr[decreaseRightIndex]) {\n            decreaseRightIndex--;\n        }\n        \n        return binSearch(0, n, increaseLeftIndex, decreaseRightIndex, arr);\n    }\n    \n    private boolean check(int value, int increaseLeftIndex, int decreaseRightIndex, int[] arr) {\n        int n = arr.length;\n        for (int i = 0; i <= n - value; i++) {\n            if (i - 1 <= increaseLeftIndex && i + value >= decreaseRightIndex &&\n                (i == 0 || i + value == n || arr[i - 1] <= arr[i + value])\n            ) {\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    private int binSearch(int left, int right, int increaseLeftIndex, int decreaseRightIndex, int[] arr) {\n        if (left >= right) return right;\n        int mid = left + (right - left) / 2;\n        return check(mid, increaseLeftIndex, decreaseRightIndex, arr) ?\n                    binSearch(left, mid, increaseLeftIndex, decreaseRightIndex, arr) :\n                    binSearch(mid + 1, right, increaseLeftIndex, decreaseRightIndex, arr);\n    }\n}\n```\n```kotlin []\nclass Solution {\n    fun findLengthOfShortestSubarray(arr: IntArray): Int {\n        var increaseLeftIndex = 0\n        while (increaseLeftIndex + 1 < arr.size && arr[increaseLeftIndex] <= arr[increaseLeftIndex + 1]) {\n            increaseLeftIndex++\n        }\n        val n = arr.size\n        var decreaseRightIndex = n - 1\n        while (decreaseRightIndex - 1 >= 0 && arr[decreaseRightIndex - 1] <= arr[decreaseRightIndex]) {\n            decreaseRightIndex--\n        }\n\n        fun check(value: Int): Boolean {\n            for (i in 0..(n - value)) {\n                if (i - 1 <= increaseLeftIndex && i + value >= decreaseRightIndex &&\n                    (i == 0 || i + value == n || arr[i - 1] <= arr[i + value])\n                ) {\n                    return true\n                }\n            }\n            return false\n        }\n\n        fun binSearch(left: Int = 0, right: Int = n): Int {\n            if (left >= right) return right\n            val mid = left + (right - left) / 2\n            return if (check(mid)) binSearch(left, mid) else binSearch(mid + 1, right)\n        }\n\n        return binSearch()\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/90bb20df-0151-4769-b980-aa2512111ae2_1731666879.4074125.png)\n
['Array', 'Binary Search', 'C++', 'Java', 'Kotlin']