CTCI 17.6

Given a 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).

CTCI 17.6.java

public static Result findUnsortedSequence(int[] input){
    /* find the left sorted sequence */
    int leftSortedSequenceEndIndex = findLeftSortedSequenceIndex(input);
    if(leftSortedSequenceEndIndex == input.length - 1) reutn Result(-1, -1);
    
    /* find the right sorted sequence */
    int rightSortedSequenceBeginIndex = findRightSortedSequenceIndex(input);
    
    /* find the biggest and samallest value in the middle */
    int biggest = Integer.MIN_VALUE; int smallest = Integer.MAX_VALUE;
    for(int i = leftSortedSequenceEndIndex; i <= rightSortedSequenceBeginIndex; i++){
        if(input[i] > biggest) biggest = input[i];
        if(input[i] < smallest) smallest = input[i];
    }
    
    /* slide left until less than smallest */
    leftSortedSequenceEndIndex = shrinkLeft(leftSortedSequenceEndIndex, smallest, input);
    
    /*slde right until bigger than biggest*/
    rightSortedSequenceBeginIndex = shinkRight(rightSortedSequenceBeginIndex, biggest, input);
    
    return Result(leftSortedSequenceEndIndex, rightSortedSequenceBeginIndex);
}