Question

Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m (that is, find the smallest such sequence).

Solution

Referring to this guy:

  1. 找到heading的最长递增序列.

  2. 找到tailing的最长的递增序列.

After that:

  1. 用中间部分的min去shrink左边.

  2. 用中间部分的max去shrink右边.

Code

written by me

public static void findUnsortedSequence(int[] array, int[] ans) {
	int len = array.length;
	ans[0] = 0;
	ans[1] = 0;

	// find increasing sequence on left and on right
	int leftPeak = 0;
	while (leftPeak < len - 1) {
		if (array[leftPeak] < array[leftPeak + 1]) {
			leftPeak++;
		} else {
			break;
		}
	}
	if (leftPeak == len - 1) {
		return;
	}
	int rightBottom = len - 1;
	while (rightBottom > 0) {
		if (array[rightBottom] > array[rightBottom - 1]) {
			rightBottom--;
		} else {
			break;
		}
	}

	// leftPeak and rightBottom are found, now read mid part
	int midMin = Integer.MAX_VALUE;
	int midMax = Integer.MIN_VALUE;
	for (int i = leftPeak; i <= rightBottom; i++) {
		midMin = Math.min(midMin, array[i]);
		midMax = Math.max(midMax, array[i]);
	}

	// find left boudary and right boundary
	int leftBound = leftPeak;
	while (leftBound >= 0) {
		if (array[leftBound] < midMin) {
			break;
		}
		leftBound--;
	}
	int rightBound = rightBottom;
	while (rightBound < len) {
		if (array[rightBound] > midMax) {
			break;
		}
		rightBound++;
	}

	// finish it up
	ans[0] = leftBound + 1;
	ans[1] = rightBound - 1;
}