Home » Data Structure » Array Data Structure

Find the minimum length unsorted subarray, sorting which makes the complete array sorted

C++ implementation to find the minimum length unsorted subarray, sorting which makes the complete array sorted.
Submitted by Vikneshwar GK, on February 05, 2022

Consider an unsorted array of size n. The task at hand is to find a subarray such that if we sort this subarray, then subsequently whole array will be sorted. The output will be the starting and ending index of this subarray.

Example:

Input:
test1[] = {1, 2, 4, 6, 8, 5, 7, 9, 10, 12}

Output:
The start and end indexes are 3 and 6

Explanation:
The subarray {6, 8, 5, 7} if sorted, 
then the whole array will be sorted.

Input:
test1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Output:
The complete array is sorted

Explanation:
Since the array is already sorted, 
there are no sub-arrays.

Solution:

This method involves using two pointers that handle the starting and ending index of the subarray. It involves the following steps:

• Step 1: Find the starting index by traversing from left to right. Starting index is the position where that element is greater than the next element, i.e array[i]>array[i+1]
• Step 2: Find the ending index by traversing from right to left. The ending index is the position where the element is lesser than its previous element, i.e array[i-1]>array[i]
• Step 3: Sort this subarray and check whether the whole array is sorted. If sorted, proceed to step 7, if not go to step 4
• Step 4: Find the minimum and maximum element in the subarray
• Step 5: From index 0 to starting index - 1, find the first element that is greater than the minimum and change the starting index to that element
• Step 6: From ending index + 1 to index n-1, find the last element that is lesser than the maximum and change the ending index to that element
• Step 7: Print the starting and ending index

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void findSubarray(int array[], int length)
{
    int start = 0, end = length - 1, i, max, min;

    // find the start index
    for (start = 0; start < length - 1; start++) {
        if (array[start] > array[start + 1])
            break;
    }
    if (start == length - 1) {
        cout << "The complete array is sorted";
        return;
    }

    // Find the ending index
    for (end = length - 1; end > 0; end--) {
        if (array[end] < array[end - 1])
            break;
    }

    // Find max and min
    max = array[start];
    min = array[start];
    for (i = start + 1; i <= end; i++) {
        if (array[i] > max)
            max = array[i];
        if (array[i] < min)
            min = array[i];
    }

    // reassign start
    for (i = 0; i < start; i++) {
        if (array[i] > min) {
            start = i;
            break;
        }
    }

    // reassign end
    for (i = length - 1; i >= end + 1; i--) {
        if (array[i] < max) {
            end = i;
            break;
        }
    }

    cout << "The start and end indexes are " << start << " and " << end;
    return;
}

// Main function
int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    // sorting the array
    findSubarray(array, N);

    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:1
Enter element 2:2
Enter element 3:4
Enter element 4:6
Enter element 5:8
Enter element 6:5
Enter element 7:7
Enter element 8:9
Enter element 9:10
Enter element 10:12
The start and end indexes are 3 and 6

Time Complexity: O(n)