Shortest Subarray to be Removed to Make Array Sorted

Medium Arrays & Hashing Two Pointer Original on LeetCode

Reported atRazorpay

Shortest Subarray to be Removed to Make Array Sorted is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every prefix and suffix pair) up.

Problem

You are given an integer array arr. Remove exactly one contiguous subarray (it may be empty) so that the elements that remain, kept in their original order, form a non-decreasing sequence.

Return the length of the shortest subarray you can remove to achieve this.

Examples

Example 1

Input
arr = [2, 4, 9, 3, 5, 7]
Output
2
Why
Removing the block [9, 3] leaves [2, 4, 5, 7]. Removing only the 9 still leaves 4 > 3, so one element is not enough.

Example 2

Input
arr = [6, 5, 4, 3]
Output
3
Why
Any two neighbours are out of order, so only one element can stay; remove the other three.

Example 3

Input
arr = [1, 2, 2, 8]
Output
0
Why
The array is already non-decreasing, so remove nothing.

Constraints

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (every prefix and suffix pair)O(n²)O(1)
Optimal (two pointers)O(n)O(1)

1Brute force (every prefix and suffix pair)

TimeO(n²)Up to n prefix ends are paired with up to n suffix starts.
SpaceO(1)Only a few indices.

The remaining array is a sorted prefix arr[0..i-1] followed by a sorted suffix arr[j..n-1]. Find how far the sorted prefix and the sorted suffix reach, then try every valid pair (i, j) and keep the smallest gap j - i whose join point is in order.

  1. L = last index of the longest non-decreasing prefix; if L == n - 1 return 0.
  2. R = first index of the longest non-decreasing suffix.
  3. For every prefix length i from 0 to L + 1 and every suffix start j from max(i, R) to n:
  4. If i == 0, or j == n, or arr[i - 1] <= arr[j], the join is valid: answer = min(answer, j - i).
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) left++;
        if (left == n - 1) return 0;
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) right--;
        int best = n;
        for (int i = 0; i <= left + 1; i++) {
            for (int j = Math.max(i, right); j <= n; j++) {
                if (i == 0 || j == n || arr[i - 1] <= arr[j]) {
                    best = Math.min(best, j - i);
                }
            }
        }
        return best;
    }
}

2Optimal (two pointers)

TimeO(n)i and right each move forward at most n times.
SpaceO(1)Only two pointers and the best value.

Start with the answer right (drop the whole part before the sorted suffix). Then grow the kept prefix one element at a time while it stays sorted. For each new prefix end arr[i], push right forward until arr[right] >= arr[i]; the block strictly between them is removed. Because the prefix values only grow, right never needs to move back.

  1. right = start of the longest non-decreasing suffix; if right == 0 return 0.
  2. best = right (keep only the suffix).
  3. For i = 0, 1, … while i < right and (i == 0 or arr[i - 1] <= arr[i]):
  4. While right < n and arr[right] < arr[i], right++.
  5. best = min(best, right - i - 1).
  6. Return best.
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) right--;
        if (right == 0) return 0;
        int best = right;
        for (int i = 0; i < right && (i == 0 || arr[i - 1] <= arr[i]); i++) {
            while (right < n && arr[right] < arr[i]) right++;
            best = Math.min(best, right - i - 1);
        }
        return best;
    }
}

Edge cases to test

  • An already sorted array (including length 1) needs 0 removals
  • A strictly decreasing array keeps only one element
  • Equal values are allowed next to each other (non-decreasing)
  • Sometimes the best answer removes a whole prefix or a whole suffix

Hints

Hint 1

What is left after removing one contiguous block? A prefix and a suffix of the original array.

Hint 2

The prefix you keep must itself be sorted, and so must the suffix. Find the longest sorted prefix and the longest sorted suffix first.

Hint 3

Glue them together: for each end of the kept prefix, the suffix must start at a value at least as large. As the prefix grows, that start only moves right, so two pointers work.

FAQ

What is the best time complexity for Shortest Subarray to be Removed to Make Array Sorted?

Optimal (two pointers) runs in O(n) time and O(1) extra space. i and right each move forward at most n times.

Which pattern does Shortest Subarray to be Removed to Make Array Sorted use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Shortest Subarray to be Removed to Make Array Sorted?

Yes. Brute force (every prefix and suffix pair) takes O(n²) time and O(1) space. The remaining array is a sorted prefix arr[0..i-1] followed by a sorted suffix arr[j..n-1].

Which edge cases should I test for Shortest Subarray to be Removed to Make Array Sorted?

An already sorted array (including length 1) needs 0 removals; A strictly decreasing array keeps only one element; Equal values are allowed next to each other (non-decreasing); Sometimes the best answer removes a whole prefix or a whole suffix.