Shortest Subarray to be Removed to Make Array Sorted

Shortest Subarray to be Removed to Make Array Sorted

What is this problem about?

The Shortest Subarray to be Removed to Make Array Sorted interview question gives you an array of integers. Find the length of the shortest contiguous subarray to remove such that the remaining elements form a non-decreasing (sorted) array. The remaining prefix and suffix must merge into a valid sorted sequence.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this problem because it tests the combination of sorted prefix/suffix identification with two-pointer merging. The key insight is finding the longest non-decreasing prefix and suffix, then using two pointers to find the minimal removal that connects them. It models data stream cleanup, removing corrupted records to restore sorted order in databases.

Algorithmic pattern used

The pattern is sorted prefix + sorted suffix + two-pointer merge. Find the longest non-decreasing prefix (ending at index left). Find the longest non-decreasing suffix (starting at index right). If the entire array is sorted, return 0. Three cases: remove everything from left+1 to end (length n - left - 1), remove from 0 to right-1 (length right), or use two pointers i from 0 and j from right: while arr[i] <= arr[j], increment i — the removal is j - i - 1. Take the minimum across all cases.

Example explanation

Array: [1, 2, 3, 10, 4, 2, 3, 5].

Sorted prefix: [1,2,3,10], left=3. Sorted suffix: [2,3,5], right=5.

Case 1: remove indices 4 to 7 → length 4. Case 2: remove indices 0 to 4 → length 5. Case 3: two pointers: i=0, j=5. arr[0]=1 ≤ arr[5]=2 → i=1. arr[1]=2 ≤ 2 → i=2. arr[2]=3 > arr[5]=2 → stop. Removal = 5-2-1=2? Actually j-i = 5-2 = 3.

Minimum: 3 (remove indices 2 to 4 → [1,2,3,5]).

Wait: removing [3,10,4] gives [1,2,2,3,5] — sorted. Removal length = 3. ✓

Common mistakes candidates make

• Only considering the three obvious cases (remove left part, right part, or middle) without the two-pointer bridge — the bridge step is what finds the optimal middle removal.
• Not validating that the merged prefix and suffix are compatible (arr[i] ≤ arr[j]).
• Off-by-one in the removal length calculation — track start and end indices carefully.
• Forgetting to check if the array is already sorted (return 0).

Interview preparation tip

For the Shortest Subarray to be Removed to Make Array Sorted coding problem, the monotonic stack two-pointer array interview pattern is the efficient approach. The two-pointer merge between the sorted prefix and suffix is the key step. Goldman Sachs and Meta interviewers test the two-pointer bridge — practice explaining why this finds the shortest middle removal. Compare each arr[i] (from prefix) with arr[j] (from suffix) and advance i as far as possible for each j. The minimum j - i - 1 across all valid (i,j) pairs gives the answer.