Shortest Subarray to be Removed to Make Array Sorted

Shortest Subarray to be Removed to Make Array Sorted - Problem

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

Input & Output

Example 1 — Middle Elements Out of Order

$ Input: arr = [1,2,3,10,4,2,3,5]

› Output: 3

💡 Note: Remove subarray [10,4,2] to get [1,2,3,3,5] which is non-decreasing. Minimum length is 3.

Example 2 — Remove Prefix

$ Input: arr = [5,4,3,2,1]

› Output: 4

💡 Note: Remove [5,4,3,2] to keep [1], or remove [4,3,2,1] to keep [5]. Both give length 4.

Example 3 — Already Sorted

$ Input: arr = [1,2,3,4]

› Output: 0

💡 Note: Array is already non-decreasing, so no elements need to be removed.

Constraints

1 ≤ arr.length ≤ 10⁵
0 ≤ arr[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [1,2,3,10,4,2,3,5] with unsorted middle section

Find Boundaries

Identify sorted prefix [1,2,3] and potential suffix connections

Optimal Removal

Remove [10,4,2] (length 3) to get sorted array [1,2,3,3,5]

Key Takeaway

🎯 Key Insight: Keep the longest sorted prefix and suffix, remove only the minimal middle section needed

Asked in

F Facebook 35 a Amazon 28 G Google 22 M Microsoft 18

The key insight is to find the longest sorted prefix and suffix, then optimally connect them. The best approach uses two pointers to achieve O(n) time complexity by identifying three removal options: remove suffix, remove prefix, or remove middle section. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Find Prefix and Suffix	O(n²)	O(1)	Find longest non-decreasing prefix and suffix, then optimally connect them
Optimized Two Pointers - Linear Time	O(n)	O(1)	Optimally find prefix and suffix with single pass and smart connecting
Brute Force - Try All Subarrays	O(n³)	O(1)	Try removing every possible subarray and check if remaining elements are sorted

Two Pointers - Find Prefix and Suffix — Algorithm Steps

Find longest non-decreasing prefix from left
Find longest non-decreasing suffix from right
Try connecting prefix elements with suffix elements
Calculate minimum removal length

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Sorted Prefix

Identify longest non-decreasing sequence from start

Find Sorted Suffix

Identify longest non-decreasing sequence from end

Connect Optimally

Find best way to connect prefix and suffix parts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* arr, int n) {
    if (n <= 1) return 0;
    
    // Find longest non-decreasing prefix
    int left = 0;
    while (left < n - 1 && arr[left] <= arr[left + 1]) {
        left++;
    }
    
    // If already sorted
    if (left == n - 1) return 0;
    
    // Find longest non-decreasing suffix
    int right = n - 1;
    while (right > 0 && arr[right - 1] <= arr[right]) {
        right--;
    }
    
    // Option 1: Remove suffix (keep prefix)
    int minRemove = right;
    
    // Option 2: Remove prefix (keep suffix)
    minRemove = min(minRemove, left + 1);
    
    // Option 3: Keep part of prefix and part of suffix
    int i = 0, j = right;
    while (i <= left && j < n) {
        if (arr[i] <= arr[j]) {
            minRemove = min(minRemove, j - i - 1);
            i++;
        } else {
            j++;
        }
    }
    
    return minRemove;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) to find prefix and suffix, then O(n²) in worst case to try all prefix-suffix combinations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for pointers and tracking positions

✓ Linear Space

32.4K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Find Prefix and Suffix — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler