Smallest Subarray to be Sorted to make the whole array sorted
Last Updated : 17 Mar, 2025
Given an unsorted array arr[]. Find the subarray arr[s...e] such that sorting this subarray makes the whole array sorted.
Note: If the given array is already sorted then return [0, 0].
Examples:
Input: arr[] = [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60]
Output: [3, 8]
Explanation: Sorting subarray starting from index 3 and ending at index 8 results in sorted array. Initial array: [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], Final array: [10, 12, 20, 25, 30, 31, 32, 35, 40, 50, 60](After sorting the bold part).
Input: arr[] = [0, 1, 15, 25, 6, 7, 30, 40, 50]
Output: [2, 5]
Explanation: Sorting subarray starting from index 2 and ending at index 5 results in sorted array. Initial array: [0, 1, 15, 25, 6, 7, 30, 40, 50], Final array: [0, 1, 6, 7, 15, 25, 30, 40, 50](After sorting the bold part).
Input: arr[] = [30, 20, 10]
Output: [0, 2]
Explanation: We need to sort the whole array to make it sorted
[Naive Approach] - Using Sorting - O(n * log n) Time and O(n) Space
The idea is create an auxiliary array temp[] equal to given array arr[], and sort the temp[] array. Now check from starting at which index the element of the given array and temporary array are unequal and store it in temporary variable s . Repeat the above From the end and store the index at another temporary variable e . The length e-s+1 is the length of smallest unequal subarray, and the indices are [s, e].
C++ #include <bits/stdc++.h> using namespace std; // Function to find the smallest subarray // sorting which makes whole array sorted vector<int> printUnsorted(vector<int> &arr) { // create the temp array equal to arr vector<int> temp = arr; // sort the temp array sort(temp.begin(), temp.end()); // to store the first and last index // with unmatching elements int s = 0, e = 0; // find the leftmost unmatching index for(int i = 0; i < arr.size(); i++) { if(arr[i] != temp[i]) { s = i; break; } } // find the rightmost unmatching index for(int i = arr.size() - 1; i >= 0; i--) { if(arr[i] != temp[i]) { e = i; break; } } return {s, e}; } int main() { vector<int> arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; vector<int> res = printUnsorted(arr); cout << res[0] << " " << res[1]; return 0; } // Function to find the smallest subarray // sorting which makes whole array sorted import java.util.*; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted static ArrayList<Integer> printUnsorted(int[] arr) { int n = arr.length; // create the temp array equal to arr int[] temp = Arrays.copyOf(arr, n); // sort the temp array Arrays.sort(temp); // to store the first and last index // with unmatching elements int s = 0, e = 0; // find the leftmost unmatching index for (int i = 0; i < n; i++) { if (arr[i] != temp[i]) { s = i; break; } } // find the rightmost unmatching index 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; } public static void main(String[] args) { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; ArrayList<Integer> res = printUnsorted(arr); System.out.println(res.get(0) + " " + res.get(1)); } } # Function to find the smallest subarray # sorting which makes whole array sorted def printUnsorted(arr): n = len(arr) # create the temp array equal to arr temp = arr[:] # sort the temp array temp.sort() # to store the first and last index # with unmatching elements s = 0 e = 0 # find the leftmost unmatching index for i in range(n): if arr[i] != temp[i]: s = i break # find the rightmost unmatching index for i in range(n - 1, -1, -1): if arr[i] != temp[i]: e = i break return [s, e] if __name__ == "__main__": arr = [0, 1, 15, 25, 6, 7, 30, 40, 50] res = printUnsorted(arr) print(res[0], res[1])
// Function to find the smallest subarray // sorting which makes whole array sorted using System; using System.Collections.Generic; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted static List<int> printUnsorted(int[] arr) { int n = arr.Length; // create the temp array equal to arr int[] temp = new int[n]; Array.Copy(arr, temp, n); // sort the temp array Array.Sort(temp); // to store the first and last index // with unmatching elements int s = 0, e = 0; // find the leftmost unmatching index for (int i = 0; i < n; i++) { if (arr[i] != temp[i]) { s = i; break; } } // find the rightmost unmatching index for (int i = n - 1; i >= 0; i--) { if (arr[i] != temp[i]) { e = i; break; } } List<int> res = new List<int> { s, e }; return res; } static void Main() { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; List<int> res = printUnsorted(arr); Console.WriteLine(res[0] + " " + res[1]); } } // Function to find the smallest subarray // sorting which makes whole array sorted. function printUnsorted(arr) { let n = arr.length; // create the temp array equal to arr let temp = arr.slice(); // sort the temp array temp.sort((a, b) => a - b); // to store the first and last index // with unmatching elements let s = 0, e = 0; // find the leftmost unmatching index for (let i = 0; i < n; i++) { if (arr[i] !== temp[i]) { s = i; break; } } // find the rightmost unmatching index for (let i = n - 1; i >= 0; i--) { if (arr[i] !== temp[i]) { e = i; break; } } return [s, e]; } let arr = [0, 1, 15, 25, 6, 7, 30, 40, 50]; let res = printUnsorted(arr); console.log(res[0] + " " + res[1]); [Better Approach] - Using Stack - O(n) Time and O(n) Space
The idea is to check each element’s nearest smaller element to its left and keep track of the maximum element seen so far. This problem mainly becomes a variation of previous smaller element.
- For each index i, find the index j of its nearest smaller element to the left using stack.
- If i - j > 1, update the left index to the minimum j encountered and the right index to i, because an element between j and i is out of order.
- If i - j ≤ 1, check if the maximum element before i is greater than arr[i]; if so, update the right index appropriately.
- The subarray to be sorted is defined from the left index + 1 to the right index, and its length is right - left.
C++ #include <bits/stdc++.h> using namespace std; // Function to find the smallest subarray // sorting which makes whole array sorted vector<int> printUnsorted(vector<int> &arr) { int n = arr.size(); // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; // to store the maximum element int maxi = INT_MIN; // stack to store the index of the elements stack<int> st; for (int i = 0; i < n; ++i) { // pop while current element is less than // the element at the top of the stack while (!st.empty() && arr[i] < arr[st.top()]) st.pop(); // if stack is not empty, then // the array is not sorted if (!st.empty()) { // update the left index if (i - st.top() > 1) { left = min(left, st.top()); right = i; } else { // if the current element is less // than the maximum element if (arr[i] < maxi) right = i; // if the element at the top of the stack // is not the maximum element else if (arr[st.top()] != maxi) right = i - 1; } } // if stack is empty else if (i != 0) { left = -1; right = i; } // update the maximum element maxi = max(maxi, arr[i]); // push the current index st.push(i); } return {left + 1, right}; } int main() { vector<int> arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; vector<int> res = printUnsorted(arr); cout << res[0] << " " << res[1]; return 0; } // Function to find the smallest subarray // sorting which makes whole array sorted import java.util.*; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted static ArrayList<Integer> printUnsorted(int[] arr) { int n = arr.length; // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; // to store the maximum element int maxi = Integer.MIN_VALUE; // stack to store the index of the elements Stack<Integer> st = new Stack<>(); for (int i = 0; i < n; ++i) { // pop while current element is less than // the element at the top of the stack while (!st.empty() && arr[i] < arr[st.peek()]) st.pop(); // if stack is not empty, then // the array is not sorted if (!st.empty()) { // update the left index if (i - st.peek() > 1) { left = Math.min(left, st.peek()); right = i; } else { // if the current element is less // than the maximum element if (arr[i] < maxi) right = i; // if the element at the top of the stack // is not the maximum element else if (arr[st.peek()] != maxi) right = i - 1; } } // if stack is empty else if (i != 0) { left = -1; right = i; } // update the maximum element maxi = Math.max(maxi, arr[i]); // push the current index st.push(i); } ArrayList<Integer> res = new ArrayList<>(); res.add(left + 1); res.add(right); return res; } public static void main(String[] args) { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; ArrayList<Integer> res = printUnsorted(arr); System.out.println(res.get(0) + " " + res.get(1)); } } # Function to find the smallest subarray # sorting which makes whole array sorted. def printUnsorted(arr): n = len(arr) # find the leftmost and rightmost index # from where the array is not sorted left = n + 1 right = -1 # to store the maximum element maxi = -float('inf') # stack to store the index of the elements st = [] for i in range(n): # pop while current element is less than # the element at the top of the stack while st and arr[i] < arr[st[-1]]: st.pop() # if stack is not empty, then # the array is not sorted if st: # update the left index if i - st[-1] > 1: left = min(left, st[-1]) right = i else: # if the current element is less # than the maximum element if arr[i] < maxi: right = i # if the element at the top of the stack # is not the maximum element elif arr[st[-1]] != maxi: right = i - 1 # if stack is empty elif i != 0: left = -1 right = i # update the maximum element maxi = max(maxi, arr[i]) # push the current index st.append(i) return [left + 1, right] if __name__ == "__main__": arr = [0, 1, 15, 25, 6, 7, 30, 40, 50] res = printUnsorted(arr) print(res[0], res[1]) // Function to find the smallest subarray // sorting which makes whole array sorted. using System; using System.Collections.Generic; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted. static List<int> printUnsorted(int[] arr) { int n = arr.Length; // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; // to store the maximum element int maxi = int.MinValue; // stack to store the index of the elements Stack<int> st = new Stack<int>(); for (int i = 0; i < n; ++i) { // pop while current element is less than // the element at the top of the stack while (st.Count > 0 && arr[i] < arr[st.Peek()]) st.Pop(); // if stack is not empty, then // the array is not sorted if (st.Count > 0) { // update the left index if (i - st.Peek() > 1) { left = Math.Min(left, st.Peek()); right = i; } else { // if the current element is less // than the maximum element if (arr[i] < maxi) right = i; // if the element at the top of the stack // is not the maximum element else if (arr[st.Peek()] != maxi) right = i - 1; } } // if stack is empty else if (i != 0) { left = -1; right = i; } // update the maximum element maxi = Math.Max(maxi, arr[i]); // push the current index st.Push(i); } List<int> res = new List<int> { left + 1, right }; return res; } static void Main() { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; List<int> res = printUnsorted(arr); Console.WriteLine(res[0] + " " + res[1]); } } // Function to find the smallest subarray // sorting which makes whole array sorted. function printUnsorted(arr) { let n = arr.length; // find the leftmost and rightmost index // from where the array is not sorted let left = n + 1, right = -1; // to store the maximum element let maxi = -Infinity; // stack to store the index of the elements let st = []; for (let i = 0; i < n; i++) { // pop while current element is less than // the element at the top of the stack while (st.length > 0 && arr[i] < arr[st[st.length - 1]]) st.pop(); // if stack is not empty, then // the array is not sorted if (st.length > 0) { // update the left index if (i - st[st.length - 1] > 1) { left = Math.min(left, st[st.length - 1]); right = i; } else { // if the current element is less // than the maximum element if (arr[i] < maxi) right = i; // if the element at the top of the stack // is not the maximum element else if (arr[st[st.length - 1]] != maxi) right = i - 1; } } // if stack is empty else if (i != 0) { left = -1; right = i; } // update the maximum element maxi = Math.max(maxi, arr[i]); // push the current index st.push(i); } return [left + 1, right]; } let arr = [0, 1, 15, 25, 6, 7, 30, 40, 50]; let res = printUnsorted(arr); console.log(res[0] + " " + res[1]); [Expected Approach] - O(n) Time and O(1) Space
The idea is to find the leftmost and rightmost index that are not following the sorted order, and then find the minimum and maximum element in subarray [left, right]. Thereafter, find the first element in [0, left - 1], which is greater than minimum, and the last element in [end + 1, n], which is smaller than maximum. These two indices are the required answer.
Follow the below given steps:
- Find the candidate unsorted subarray
- Scan from left to right and find the first element which is greater than the next element.
- Scan from right to left and find the first element which is smaller than the next element.
- Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
- Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max.
- Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.
- Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.
- Print s and e.
Below is the implementation of the above approach:
C++ #include <bits/stdc++.h> using namespace std; // Function to find the smallest subarray // sorting which makes whole array sorted vector<int> printUnsorted(vector<int> &arr) { int n = arr.size(); // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; for(int i = 0; i < n - 1; i++) { if(arr[i] > arr[i + 1]) { left = i; break; } } // if array is already sorted if(left == n + 1) { return {0, 0}; } for(int i = n - 1; i > 0; i--) { if(arr[i] < arr[i - 1]) { right = i; break; } } // find the maximum and minimum element 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]); } // find the correct position // of the minimum element for(int i = 0; i < left; i++) { if(arr[i] > mini) { left = i; break; } } // find the correct position // of the maximum element for(int i = n - 1; i > right; i--) { if(arr[i] < maxi) { right = i; break; } } return {left, right}; } int main() { vector<int> arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; vector<int> res = printUnsorted(arr); cout << res[0] << " " << res[1]; return 0; } // Function to find the smallest subarray // sorting which makes whole array sorted import java.util.*; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted static ArrayList<Integer> printUnsorted(int[] arr) { int n = arr.length; // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { left = i; break; } } // if array is already sorted if (left == n + 1) { ArrayList<Integer> res = new ArrayList<>(); res.add(0); res.add(0); return res; } for (int i = n - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { right = i; break; } } // find the maximum and minimum element int maxi = arr[left], mini = arr[left]; for (int i = left + 1; i <= right; i++) { maxi = Math.max(maxi, arr[i]); mini = Math.min(mini, arr[i]); } // find the correct position // of the minimum element for (int i = 0; i < left; i++) { if (arr[i] > mini) { left = i; break; } } // find the correct position // of the maximum element for (int i = n - 1; i > right; i--) { if (arr[i] < maxi) { right = i; break; } } ArrayList<Integer> res = new ArrayList<>(); res.add(left); res.add(right); return res; } public static void main(String[] args) { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; ArrayList<Integer> res = printUnsorted(arr); System.out.println(res.get(0) + " " + res.get(1)); } } # Function to find the smallest subarray # sorting which makes whole array sorted. def printUnsorted(arr): n = len(arr) # find the leftmost and rightmost index # from where the array is not sorted left = n + 1 right = -1 for i in range(n - 1): if arr[i] > arr[i + 1]: left = i break # if array is already sorted if left == n + 1: return [0, 0] for i in range(n - 1, 0, -1): if arr[i] < arr[i - 1]: right = i break # find the maximum and minimum element maxi = arr[left] mini = arr[left] for i in range(left + 1, right + 1): maxi = max(maxi, arr[i]) mini = min(mini, arr[i]) # find the correct position # of the minimum element for i in range(left): if arr[i] > mini: left = i break # find the correct position # of the maximum element for i in range(n - 1, right, -1): if arr[i] < maxi: right = i break return [left, right] if __name__ == "__main__": arr = [0, 1, 15, 25, 6, 7, 30, 40, 50] res = printUnsorted(arr) print(res[0], res[1])
// Function to find the smallest subarray // sorting which makes whole array sorted. using System; using System.Collections.Generic; class GfG { // Function to find the smallest subarray // sorting which makes whole array sorted. static List<int> printUnsorted(int[] arr) { int n = arr.Length; // find the leftmost and rightmost index // from where the array is not sorted int left = n + 1, right = -1; for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { left = i; break; } } // if array is already sorted if (left == n + 1) { return new List<int> { 0, 0 }; } for (int i = n - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { right = i; break; } } // find the maximum and minimum element int maxi = arr[left], mini = arr[left]; for (int i = left + 1; i <= right; i++) { maxi = Math.Max(maxi, arr[i]); mini = Math.Min(mini, arr[i]); } // find the correct position // of the minimum element for (int i = 0; i < left; i++) { if (arr[i] > mini) { left = i; break; } } // find the correct position // of the maximum element for (int i = n - 1; i > right; i--) { if (arr[i] < maxi) { right = i; break; } } return new List<int> { left, right }; } static void Main() { int[] arr = {0, 1, 15, 25, 6, 7, 30, 40, 50}; List<int> res = printUnsorted(arr); Console.WriteLine(res[0] + " " + res[1]); } } // Function to find the smallest subarray // sorting which makes whole array sorted. function printUnsorted(arr) { let n = arr.length; // find the leftmost and rightmost index // from where the array is not sorted let left = n + 1, right = -1; for (let i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { left = i; break; } } // if array is already sorted if (left === n + 1) return [0, 0]; for (let i = n - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { right = i; break; } } // find the maximum and minimum element let maxi = arr[left], mini = arr[left]; for (let i = left + 1; i <= right; i++) { maxi = Math.max(maxi, arr[i]); mini = Math.min(mini, arr[i]); } // find the correct position // of the minimum element for (let i = 0; i < left; i++) { if (arr[i] > mini) { left = i; break; } } // find the correct position // of the maximum element for (let i = n - 1; i > right; i--) { if (arr[i] < maxi) { right = i; break; } } return [left, right]; } let arr = [0, 1, 15, 25, 6, 7, 30, 40, 50]; let res = printUnsorted(arr); console.log(res[0] + " " + res[1]); Similar Reads
Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order. There exist different sorting algorithms for differ
3 min read
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure. Why Sorting Algorithms are ImportantThe sorting algorithm is important in Com
3 min read
Most Common Sorting Algorithms
Selection Sort Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.First we find the smallest element an
8 min read
Bubble Sort Algorithm Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.We sort the array using multiple passes. After the fir
8 min read
Insertion Sort Algorithm Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. T
9 min read
Merge Sort - Data Structure and Algorithms Tutorials Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. Merge
14 min read
Quick Sort QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. It works on the principle of divide and conquer, breaking down the problem into s
12 min read
Heap Sort - Data Structures and Algorithms Tutorials Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It can be seen as an optimization over selection sort where we first find the max (or min) element and swap it with the last (or first). We repeat the same process for the remaining elements. In Heap Sort, we use
14 min read
Counting Sort - Data Structures and Algorithms Tutorials Counting Sort is a non-comparison-based sorting algorithm. It is particularly efficient when the range of input values is small compared to the number of elements to be sorted. The basic idea behind Counting Sort is to count the frequency of each distinct element in the input array and use that info
9 min read