Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted.

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted.

---

Find minimum unsorted subarray index m and n such that if you sort elements from m through n, then complete array would be sorted.

Let's understand the problem statement in simple words, 
Given an array of partially sorted integers, you have to find start index 'm' from where mismatch started that is the point from which array is not in sorted order,  and you have to find index 'n' till which index array is unsorted, and if you sort elements m through n, then entire array would be sorted.  

Let's see example to understand what is the input and expected output.

Find smallest window in array sorting which will make entire array sorted

Algorithm

---

For finding unsorted subarray index 'm' and 'n', First, we will analyze the given array property, that is Array is partially sorted except for in between index 'm' and 'n'.

We can use this property to find till what index Array is sorted and ultimately we will get till where it is unsorted.

Case 1: Given array is completly sorted

First how to find that array is sorted or not, 

1. Traverse from i=0 to array length. and check if arr[i] < arr[i+1], 
2. If you don't found any mismatch then array is sorted.

If you found any mismatch, then array is not completly sorted and we need to find start and end index of subarray, sorting which complete array will be sorted. See Case 2.

Case 2: Given array is partially sorted  

For this case, we will first find, starting from index 0, till what index array is sorted.
For this, Iterate array from i=0 to array.length, Point where you see (arr[i] > arr[i+1]), that is the place where mismatch started and before that point array is already sorted.

We found index "x", such that starting from 0th index till "x" index array is already sorted.
In similar way we need to find index "y" from end, till place where array is already sorted.

Now we have to find the mismatch from end as well,
For this, Iterate array from i=array.length to 0, Point where you see (arr[i] < arr[i-1]), that is the place where mismatch started and till that point array is already sorted from end.

We found index "y", such that starting from end till "y" index, array is sorted.

Now we have 2 index, "x" and "y"
x index = index where mismatch started from left side, and 
y index =  index where mismatch started from right side.

 
Finding minimum and maximum element between "x" and "y".

Now to find the unsorted subarray index, we need to find out minimum and maximum element present in the bunch of elements between "x" and "y".

For this, iterate from i=x till i<=y, find minimum element (minItem) and maximum element (maxItem) between them.
 

Finding unsorted subarray index using minItem and maxItem

Once the minimum element (minItem) in bunch is known, now to find start of unsorted subarray index "m", Traverse array from left till you find the element greater than minItem, that will be starting index of unsorted array.

Once the maximum element (maxItem) in bunch is known, now to find end of unsorted subarray index "n", Traverse from right till you find the element smaller than maxItem, that will be ending index of unsorted array.


Java Program to find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted.

---

package javabypatel;

public class MinimumLengthUnsortedSubarrayIndexInSortedArray {
 public static void main(String[] args) {

  //int arr[] = {6,8,10, 15, 12,30,9,22, 45,50,55};
  int arr[] = {10,20,40,50,30,15,95,70,90,100};
  
  findIndexOfUnsortedSubArray(arr);
 }

 private static void findIndexOfUnsortedSubArray(int arr[]){
  int leftMismatchIndex = findMismatchFromLeft(arr);
  if(leftMismatchIndex == -1){
   System.out.println("Array is already sorted");
   return;
  }
  int rightMismatchIndex = findMismatchFromRight(arr);  
  int lIndex = leftMismatchIndex; 
  int rIndex = rightMismatchIndex;

  //Now, find Minimum and Maximum element between lIndex and rIndex.
  int min = arr[lIndex];
  int max = arr[rIndex];
  for (int i = lIndex; i <= rIndex; i++) {
   if(arr[i]<min){
    min = arr[i];
   }
   if(arr[i]>max){
    max = arr[i];
   }
  }
  
  //Find unsorted subarray startIndex and endIndex.
  int startIndex = findMinimumElementBetween(arr, min, 0, lIndex);
  int endIndex = findMaximumElementBetween(arr, max, arr.length-1, rIndex);
  
  System.out.println(startIndex + " " + endIndex);
 }

 private static int findMismatchFromLeft(int arr[]){
  for (int i = 1; i < arr.length; i++) { 
   if(arr[i-1]>arr[i]){
    return i-1;
   }
  }
  return -1;
 }

 private static int findMismatchFromRight(int arr[]){
  for (int i = arr.length-1; i >= 0; i--) { 
   if(arr[i]<arr[i-1]){
    return i;
   }
  }
  return -1;
 }

 private static int findMinimumElementBetween(int arr[], int min, int start, int end){
  for (int i = start; i <= end; i++) {
   if(arr[i]>min){
    return i;
   }
  }
  return -1;
 }

 private static int findMaximumElementBetween(int arr[], int max, int start, int end){
  for (int i = start; i >= end; i--) {
   if(arr[i]<max){
    return i;
   }
  }
  return -1;
 }
}

You may also like to see

---

Count trailing zeros in factorial of a number.

Swap two numbers In Java without using third variable - Best Approach.

Breadth First Search(BFS) Vs Depth First Search(DFS) with example in Java

Can static method be called using object in java

Method overriding and Method hiding Interview Question in Java.

When to use SOAP over REST Web Service. Is REST better than SOAP?.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.