Binary Search | Java | Easy to Understand Solution
There are three cases:\n1. We remove a prefix, such that remaining elements in array are non-decreasing.\nExample : array[] = [12,15,7,8,8,9,10]\nWe remove pref
There are three cases:\n1. We remove a prefix, such that remaining elements in array are non-decreasing.\nExample : array[] = [12,15,7,8,8,9,10]\nWe remove prefix [12,15], and we are left with [7,8,8,9,10].\n2. We remove a suffix, such that remaining elements in array are non-decreasing.\nExample : array[] = [3,4,5,5,1,2]\nWe remove suffix [1,2], and we are left with [3,4,5,5].\n\n3.  We remove a subarray (not prefix or suffix).\nExample : arr[] = [1,2,3,10,4,2,3,5]\nSo, now we divide our arr into 3 parts, [left, middle, right] such that,\nleft[] and right[] are non-decreasing.\nAnd middle[] is the part we are removing.\nNow  left[] + right[] should form non-decreasing array.\nSo for each k from [0, i), we try to remove prefix[0, k] and try to find lowest index(lo) in right array such that array[lo] >= array[k] using Binary Search.\n\nNote: The left and right merge can be optimized using two pointer technique.\n\nExample\n\n```\n[------left]  [----middle------]   [right-----]\n[1, 2, 3, 10  ( ----4----------)   2,  3,    5]\n 0     k          i            j       lo   n-1\n         [10  ------removed-----   2]                                                   \n```\n\n\nUsing Binary Search\n```\nclass Solution {\n    public int findLengthOfShortestSubarray(int[] arr) {\n        int n = arr.length;\n        int i = 0, j = n - 1;\n        int maxSeen = 0;\n        while (i < n && arr[i] >= maxSeen) {\n            maxSeen = arr[i];\n            i++;\n        }\n        int minSeen = Integer.MAX_VALUE;\n        while (j >= 0 && arr[j] <= minSeen) {\n            minSeen = arr[j];\n            j--;\n        }\n        int shortestSubarry = Math.min(n - i, j + 1);\n        if (i == n || j == -1) {\n            return shortestSubarry;\n        }\n        for (int k = 0; k < i; k++) {\n            int lo = binarySearch(arr, j + 1, n - 1, arr[k]);\n            if (lo == -1) {\n                continue;\n            }\n            shortestSubarry = Math.min(shortestSubarry, lo - k - 1);\n        }\n        return shortestSubarry;\n    }\n    private int binarySearch(int[] arr, int lo, int hi, int value) {\n        while (lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if (arr[mid] >= value) {\n                hi = mid;\n            }else {\n                lo = mid + 1;\n            }\n        }\n        return arr[lo] >= value ? lo : -1;\n    }\n}\n```\n\nUsing Two Pointer \n```\nclass Solution {\n    public int findLengthOfShortestSubarray(int[] arr) {\n        int n = arr.length;\n        int i = 0, j = n - 1;\n        int maxSeen = 0;\n        while (i < n && arr[i] >= maxSeen) {\n            maxSeen = arr[i];\n            i++;\n        }\n        int minSeen = Integer.MAX_VALUE;\n        while (j >= 0 && arr[j] <= minSeen) {\n            minSeen = arr[j];\n            j--;\n        }\n        int shortestSubarry = Math.min(n - i, j + 1);\n        if (i == n || j == -1) {\n            return shortestSubarry;\n        }\n        int lo = 0, hi = j + 1;\n        while (lo < i && hi < arr.length) {\n            if (arr[hi] >= arr[lo]) {\n                shortestSubarry = Math.min(shortestSubarry, hi - lo - 1);\n                lo++;\n            }else {\n                hi++;\n            }\n        }\n        return shortestSubarry;\n    }\n}\n```\n\nIf you like the solution, please Upvote \uD83D\uDC4D!!\n\n\n
[]