Mastering the Smallest Subarray Sorting Problem

Have you ever encountered a situation where you needed to sort an entire array, but you realized that only a small portion of the array was actually out of order? This is the essence of the "Smallest Subarray to be Sorted to make the whole array sorted" problem, a common and important challenge in the world of data structures and algorithms.

In this comprehensive article, we‘ll dive deep into this problem, exploring various approaches to solve it efficiently, and understanding the trade-offs between different solutions. By the end, you‘ll have a solid grasp of this problem and be equipped with the knowledge to tackle it in your own programming endeavors.

Understanding the Problem

The "Smallest Subarray to be Sorted to make the whole array sorted" problem can be stated as follows:

Given an unsorted array arr, find the subarray arr[s...e] such that sorting this subarray makes the whole array sorted.

In other words, we need to identify the smallest contiguous subarray that, when sorted, will result in the entire array being in sorted order.

Let‘s consider a few examples to better understand the problem:

Example 1:

Input: arr[] = [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60]
Output: [3, 8]
Explanation: Sorting the subarray [25, 40, 32, 31, 35] makes the whole array sorted.

Example 2:

Input: arr[] = [0, 1, 15, 25, 6, 7, 30, 40, 50]
Output: [2, 5]
Explanation: Sorting the subarray [15, 25, 6, 7] makes the whole array sorted.

Example 3:

Input: arr[] = [30, 20, 10]
Output: [0, 2]
Explanation: We need to sort the whole array to make it sorted.

In the first two examples, the input arrays are not completely sorted, and we need to identify the smallest subarray that, when sorted, will make the entire array sorted. In the third example, the array is already in descending order, so we need to sort the entire array to make it sorted.

Naive Approach: Using Sorting

One of the simplest approaches to solve this problem is to use sorting. The idea is to create an auxiliary array temp that is a copy of the original array arr, sort the temp array, and then compare the elements of the original array with the sorted temp array to find the leftmost and rightmost indices where the elements are not matching.

Here‘s the step-by-step implementation of this approach:

1. Create a temporary array temp that is a copy of the original array arr.
2. Sort the temp array using a sorting algorithm (e.g., quicksort, mergesort, etc.).
3. Iterate through the original array arr from left to right and find the first index s where the element of arr is different from the corresponding element in the sorted temp array.
4. Iterate through the original array arr from right to left and find the first index e where the element of arr is different from the corresponding element in the sorted temp array.
5. The subarray arr[s...e] is the smallest subarray that needs to be sorted to make the entire array sorted.

Here‘s the implementation in various programming languages:

// C++ implementation
vector<int> printUnsorted(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp = arr;
    sort(temp.begin(), temp.end());
    int s = 0, e = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != temp[i]) {
            s = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (arr[i] != temp[i]) {
            e = i;
            break;
        }
    }
    return {s, e};
}

// Java implementation
static ArrayList<Integer> printUnsorted(int[] arr) {
    int n = arr.length;
    int[] temp = Arrays.copyOf(arr, n);
    Arrays.sort(temp);
    int s = 0, e = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != temp[i]) {
            s = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (arr[i] != temp[i]) {
            e = i;
            break;
        }
    }
    ArrayList<Integer> res = new ArrayList<>();
    res.add(s);
    res.add(e);
    return res;
}

# Python implementation
def printUnsorted(arr):
    n = len(arr)
    temp = arr[:]
    temp.sort()
    s = 0
    e = 0
    for i in range(n):
        if arr[i] != temp[i]:
            s = i
            break
    for i in range(n - 1, -1, -1):
        if arr[i] != temp[i]:
            e = i
            break
    return [s, e]

The time complexity of this approach is O(n * log n) due to the sorting step, and the space complexity is O(n) due to the creation of the temporary array.

While this approach is straightforward and easy to understand, it has a major drawback: it requires creating an additional array and sorting it, which can be inefficient for large input sizes. In the next section, we‘ll explore a more efficient approach using a stack-based solution.

Better Approach: Using Stack

The idea behind this approach is to use a stack to keep track of the indices of the elements and find the nearest smaller element to the left of each element. This information can be used to determine the leftmost and rightmost indices of the subarray that needs to be sorted.

Here‘s the step-by-step implementation of this approach:

1. Initialize variables left and right to store the leftmost and rightmost indices of the subarray that needs to be sorted. Set left to n + 1 and right to -1.
2. Initialize a variable maxi to store the maximum element seen so far.
3. Use a stack to store the indices of the elements.
4. Iterate through the array from left to right:
   • While the current element is less than the element at the top of the stack, pop the stack.
   • If the stack is not empty, update the left and right indices based on the following conditions:
     • If the distance between the current index and the index at the top of the stack is greater than 1, update left to the minimum of the current left and the index at the top of the stack, and update right to the current index.
     • If the distance between the current index and the index at the top of the stack is 1 or less, check if the current element is less than the maximum element seen so far. If so, update right to the current index. If the element at the top of the stack is not the maximum element, update right to the previous index.
   • If the stack is empty and the current index is not the first index, set left to -1 and right to the current index.
   • Update the maxi variable to the maximum of the current maxi and the current element.
   • Push the current index onto the stack.
5. Return the left and right indices.

Here‘s the implementation in various programming languages:

// C++ implementation
vector<int> printUnsorted(vector<int>& arr) {
    int n = arr.size();
    int left = n + 1, right = -1;
    int maxi = INT_MIN;
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && arr[i] < arr[st.top()])
            st.pop();
        if (!st.empty()) {
            if (i - st.top() > 1) {
                left = min(left, st.top());
                right = i;
            } else {
                if (arr[i] < maxi)
                    right = i;
                else if (arr[st.top()] != maxi)
                    right = i - 1;
            }
        } else if (i != 0) {
            left = -1;
            right = i;
        }
        maxi = max(maxi, arr[i]);
        st.push(i);
    }
    return {left + 1, right};
}

// Java implementation
static ArrayList<Integer> printUnsorted(int[] arr) {
    int n = arr.length;
    int left = n + 1, right = -1;
    int maxi = Integer.MIN_VALUE;
    Stack<Integer> st = new Stack<>();
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && arr[i] < arr[st.peek()])
            st.pop();
        if (!st.empty()) {
            if (i - st.peek() > 1) {
                left = Math.min(left, st.peek());
                right = i;
            } else {
                if (arr[i] < maxi)
                    right = i;
                else if (arr[st.peek()] != maxi)
                    right = i - 1;
            }
        } else if (i != 0) {
            left = -1;
            right = i;
        }
        maxi = Math.max(maxi, arr[i]);
        st.push(i);
    }
    ArrayList<Integer> res = new ArrayList<>();
    res.add(left + 1);
    res.add(right);
    return res;
}

# Python implementation
def printUnsorted(arr):
    n = len(arr)
    left = n + 1
    right = -1
    maxi = -float(‘inf‘)
    st = []
    for i in range(n):
        while st and arr[i] < arr[st[-1]]:
            st.pop()
        if st:
            if i - st[-1] > 1:
                left = min(left, st[-1])
                right = i
            else:
                if arr[i] < maxi:
                    right = i
                elif arr[st[-1]] != maxi:
                    right = i - 1
        elif i != 0:
            left = -1
            right = i
        maxi = max(maxi, arr[i])
        st.append(i)
    return [left + 1, right]

The time complexity of this approach is O(n), and the space complexity is O(n) due to the use of the stack.

This approach is more efficient than the naive approach, as it doesn‘t require sorting the entire array. Instead, it uses the stack to keep track of the indices of the elements and determines the leftmost and rightmost indices of the subarray that needs to be sorted.

Expected Approach: O(n) Time and O(1) Space

The expected approach to solve this problem is to find the leftmost and rightmost indices of the subarray that needs to be sorted, and then find the minimum and maximum elements in that subarray. Finally, we need to find the first element in the left part of the array that is greater than the minimum element, and the last element in the right part of the array that is smaller than the maximum element.

Here‘s the step-by-step implementation of this approach:

1. Find the leftmost and rightmost indices of the subarray that needs to be sorted:
   • Scan the array from left to right and find the first element that is greater than the next element. This index is the leftmost index of the subarray.
   • Scan the array from right to left and find the first element that is smaller than the next element. This index is the rightmost index of the subarray.
2. If the array is already sorted, return [0, 0].
3. Find the minimum and maximum elements in the subarray arr[left...right].
4. Find the first element in arr[0...left-1] that is greater than the minimum element, and update the left index accordingly.
5. Find the last element in arr[right+1...n-1] that is smaller than the maximum element, and update the right index accordingly.
6. Return the left and right indices.

Here‘s the implementation in various programming languages:

// C++ implementation
vector<int> printUnsorted(vector<int>& arr) {
    int n = arr.size();
    int left = n + 1, right = -1;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            left = i;
            break;
        }
    }
    if (left == n + 1) {
        return {0, 0};
    }
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] < arr[i - 1]) {
            right = i;
            break;
        }
    }
    int maxi = arr[left], mini = arr[left];
    for (int i = left + 1; i <= right; i++) {
        maxi = max(maxi, arr[i]);
        mini = min(mini, arr[i]);
    }
    for (int i = 0; i < left; i++) {
        if (arr[i] > mini) {
            left = i;
            break;
        }
    }
    for (int i = n - 1; i > right; i--) {
        if (arr[i] < maxi) {
            right = i;
            break;
        }
    }
    return {left, right};
}

// Java implementation
static ArrayList<Integer> printUnsorted(int[] arr) {
    int n = arr.length;
    int left = n + 1, right = -1;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            left = i;
            break;
        }
    }
    if (left == n + 1) {
        return new ArrayList<>(Arrays.asList(0, 0));
    }
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] < arr[i - 1]) {
            right = i;
            break;
        }
    }
    int maxi = arr[left], mini = arr[left];
    for (int i = left + 1; i <= right; i++) {
        maxi = Math.max(maxi, arr[i]);
        mini =