Shortest Unsorted Continuous Subarray - Practice Coding Problems

Shortest Unsorted Continuous Subarray - Problem

Array Two Pointers Stack Greedy Sorting Monotonic Stack Medium

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the length of the shortest such subarray.

Note: The array may already be sorted, in which case the answer is 0.

Input & Output

Example 1 — Basic Unsorted Middle

$ Input: nums = [2,6,4,8,10,9,15]

› Output: 5

💡 Note: Need to sort subarray [6,4,8,10,9] from index 1 to 5. After sorting it becomes [4,6,8,9,10], making the whole array [2,4,6,8,9,10,15] which is fully sorted. Length = 5.

Example 2 — Already Sorted

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

› Output: 0

💡 Note: The array is already sorted in non-decreasing order, so no subarray needs to be sorted. Return 0.

Example 3 — Entire Array Unsorted

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

› Output: 5

💡 Note: The entire array is in reverse order. We need to sort the whole array [5,4,3,2,1] to get [1,2,3,4,5]. Length = 5.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with some elements out of order

Find Boundaries

Identify the shortest subarray to sort

Result

Length of the unsorted subarray

Key Takeaway

🎯 Key Insight: Find the leftmost element that's larger than some element to its right, and the rightmost element that's smaller than some element to its left.

Asked in

G Google 42 a Amazon 38 M Microsoft 25 f Facebook 18

The key insight is finding elements that violate sorted order: elements smaller than the maximum seen so far (from left), and elements larger than the minimum seen so far (from right). The optimal two pointers approach runs in O(n) time with O(1) space by tracking these boundary violations in two passes.

Common Approaches

Approach	Time	Space	Notes
✓ Compare with Sorted Array	O(n log n)	O(n)	Sort the array and compare with original to find the leftmost and rightmost differences
Two Pointers Optimal	O(n)	O(1)	Find the leftmost and rightmost elements that are out of place using min/max tracking
Check All Subarrays	O(n⁴)	O(n)	Try every possible subarray and check if sorting it makes the whole array sorted

Compare with Sorted Array — Algorithm Steps

Step 1: Create a sorted copy of the array
Step 2: Find leftmost position where original differs from sorted
Step 3: Find rightmost position where original differs from sorted
Step 4: Return the distance between these boundaries

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Copy

Create sorted version of array

Find Boundaries

Locate first and last differences

Calculate Length

Distance between boundaries

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;
    
    // Create sorted copy
    int* sortedNums = (int*)malloc(numsSize * sizeof(int));
    memcpy(sortedNums, nums, numsSize * sizeof(int));
    qsort(sortedNums, numsSize, sizeof(int), compare);
    
    // Find leftmost difference
    int left = 0;
    while (left < numsSize && nums[left] == sortedNums[left]) {
        left++;
    }
    
    // Find rightmost difference
    int right = numsSize - 1;
    while (right >= 0 && nums[right] == sortedNums[right]) {
        right--;
    }
    
    free(sortedNums);
    
    // If left > right, array is already sorted
    return (right < left) ? 0 : right - left + 1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int count = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the array takes O(n log n), comparison is O(n)

⚡ Linearithmic

Space Complexity

O(n)

Extra array needed to store sorted copy

⚡ Linearithmic Space

197.2K Views

High Frequency

~25 min Avg. Time

6.8K 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

Compare with Sorted Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler