Interview Program – Array

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

About the author

Bushan Sirgur

Hey guys, I am Bushan Sirgur from Banglore, India. Currently, I am working as an Associate project in an IT company.

View all posts

Leave a Reply

Your email address will not be published. Required fields are marked *