Subarray Sort

Tags

Subarray Sort

Category

Arrays

Difficulty

Hard

Problem Statement

Given an array of integers, find the smallest subarray that needs to be sorted in place so that the entire array becomes sorted in ascending order. Return the start and end indices of this subarray. If the array is already sorted, return [-1, -1].

Intuition

If we sort the entire array and compare it to the original, the first and last positions where they differ mark our answer. However, we can do better without sorting. The key observation is: any element that is out of order must be inside the subarray we need to sort. An element is "out of order" if it is smaller than an element to its left or larger than an element to its right. Once we identify the minimum and maximum of all out-of-order elements, we find where those values would correctly sit in the sorted portions of the array.

Approach

  1. Traverse the array and identify all elements that are out of order. An element at index i is out of order if array[i] < array[i-1] or array[i] > array[i+1].
  2. Find the minimum and maximum values among all out-of-order elements.
  3. Find the correct position for the minimum value by scanning from the left until we find an element greater than this minimum. This is the start index.
  4. Find the correct position for the maximum value by scanning from the right until we find an element smaller than this maximum. This is the end index.
  5. Return [startIndex, endIndex].

Pseudocode

function subarraySort(array):
    minOutOfOrder = +infinity
    maxOutOfOrder = -infinity

    for i from 0 to length(array) - 1:
        if isOutOfOrder(i, array):
            minOutOfOrder = min(minOutOfOrder, array[i])
            maxOutOfOrder = max(maxOutOfOrder, array[i])

    if minOutOfOrder == +infinity:
        return [-1, -1]

    leftIdx = 0
    while array[leftIdx] <= minOutOfOrder:
        leftIdx++

    rightIdx = length(array) - 1
    while array[rightIdx] >= maxOutOfOrder:
        rightIdx--

    return [leftIdx, rightIdx]

function isOutOfOrder(i, array):
    if i == 0:
        return array[i] > array[i + 1]
    if i == length(array) - 1:
        return array[i] < array[i - 1]
    return array[i] > array[i + 1] or array[i] < array[i - 1]

Time & Space Complexity

  • Time: O(n) — We make a constant number of linear passes through the array.
  • Space: O(1) — Only a fixed number of variables are used regardless of input size.

Key Insights

  • We do not actually need to sort anything. The problem reduces to finding the min and max of the "unsorted portion" and then determining where those extremes belong.
  • An element can be out of order relative to its left neighbor, its right neighbor, or both.
  • The first and last elements are special cases since they only have one neighbor each.

Edge Cases

  • Already sorted array: return [-1, -1].
  • Array of length 1: always sorted, return [-1, -1].
  • Entire array is reversed: the subarray is the full array.
  • Only two elements are swapped: the subarray spans exactly those two positions.
  • Array with duplicate values: the out-of-order check must use strict inequalities carefully to handle equal adjacent elements.

Linked mentions