1 ms | Beats 100 %
Intuition\nThe intuition behind this code is to find the length of the shortest subarray that can be removed from the array arr so that the resulting array is n
# Intuition\nThe intuition behind this code is to find the length of the shortest subarray that can be removed from the array arr so that the resulting array is non-decreasing.\n\n# Approach\nIdentify the Longest Non-Decreasing Prefix:\n\nStart from the beginning of arr and find the longest non-decreasing sequence arr[0..l].\nl is the index of the last element in this sequence.\nIdentify the Longest Non-Decreasing Suffix:\n\nSimilarly, start from the end of arr and find the longest non-decreasing sequence arr[r..n-1].\nr is the index of the first element in this sequence when traversing from the end.\nSimple Case Check:\n\nIf l reaches the last element (l == n - 1), then arr is already sorted in non-decreasing order, so no elements need to be removed. The result is 0.\nCompute Initial Minimum Removals:\n\nConsider two initial options to remove elements:\nRemove all elements from arr[l + 1] to the end of the array, which would leave only the prefix.\nRemove all elements from the start of the array to arr[r - 1], which would leave only the suffix.\nThe length of these two options is n - 1 - l and r, respectively, and the minimum of the two is stored in ans.\nMerge the Prefix and Suffix:\n\nTo potentially minimize the removable section further, attempt to combine elements from the end of the prefix (arr[0..l]) with elements from the start of the suffix (arr[r..n-1]) by ensuring they form a non-decreasing sequence.\nUse two pointers:\ni, starting at l, and\nj, starting at r.\nMove j leftward if arr[i] <= arr[j] (allowing a merge), and move i leftward otherwise.\nUpdate ans to be the minimum of its current value and the section length j - i.\nReturn the Result:\n\nAfter attempting all combinations, ans will hold the smallest length of a subarray to remove, achieving the objective.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```java []\nclass Solution {\n  public int findLengthOfShortestSubarray(int[] arr) {\n    final int n = arr.length;\n    int l = 0;\n    int r = n - 1;\n    while (l < n - 1 && arr[l + 1] >= arr[l])\n      ++l;\n   \n    while (r > 0 && arr[r - 1] <= arr[r])\n      --r;\n    int ans = Math.min(n - 1 - l, r);\n\n    int i = l;\n    int j = n - 1;\n    while (i >= 0 && j >= r && j > i) {\n      if (arr[i] <= arr[j])\n        --j;\n      else\n        --i;\n      ans = Math.min(ans, j - i);\n    }\n\n    return ans;\n  }\n}\n```
['Array', 'Two Pointers', 'Binary Search', 'Stack', 'Monotonic Stack', 'Java']