Find the length of unsorted subarray such that sorting this subarray can sort all the array. Print the start and end index.
public class Solution {
public static void unsortedArrayIndex(int ar[]) {
int i = 0;
int j = ar.length - 1;
boolean startIndex = true;
boolean endIndex = true;
int indexStart = -1;
int indexEnd = -1;
// finding position of unsorted array
while (true) {
if (ar[i] > ar[i + 1]) {
if (startIndex) {
indexStart = i + 1;
startIndex = false;
}
}
i++;
if (ar[j] < ar[j - 1]) {
if (endIndex) {
indexEnd = j - 1;
endIndex = false;
}
}
j--;
if (i > j || (!startIndex && !endIndex))
break;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
if (!startIndex || !endIndex) {
// checking max and mean in unsorted array
for (int k = indexStart; k <= indexEnd; k++) {
if (max < ar[k]) {
max = ar[k];
}
if (min > ar[k]) {
min = ar[k];
}
}
// checking if any index in left of array is larger than minimum of
// unsorted array
for (int k = 0; k < indexStart; k++) {
if (ar[k] > min) {
indexStart = k;
}
}
// checking if any index in right of array is smaller than max of
// unsorted array
for (int k = ar.length - 1; k >= indexEnd; k--) {
if (ar[k] < max) {
indexEnd = k;
}
}
}
System.out.print(indexStart + " " + indexEnd);
}
public static void main(String[] args) {
int[] arr = { 10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60 };
unsortedArrayIndex(arr);
}
}
Thanks and Regards
Solution Provided by Nilmani Prashanth
