Maximum Unsorted Subarray

You are given an array (zero indexed) of N non-negative integers, A0, A1 ,…, AN-1.
Find the minimum sub array Al, Al+1 ,…, Ar so if we sort(in ascending order) that sub array, then the whole array should get sorted.
If A is already sorted, output -1.

Example :
Input 1:

A = [1, 3, 2, 4, 5]

Return: [1, 2]

Input 2:

A = [1, 2, 3, 4, 5]

Return: [-1]
In the above example(Input 1), if we sort the subarray A1, A2, then whole array A should get sorted.

思路1

建一个sort好的array，然后两头往里看，分别找第一个不一样的element即是我们要的A1和A2。

Solution1:

Time: O(nlogn)
Space: O(n)

public class Solution {
    public ArrayList<Integer> subUnsort(ArrayList<Integer> A) {
        ArrayList<Integer> sorted = new ArrayList<>(A);
        Collections.sort(A);
        int left = -1;
        int right = -1;
        for (int i = 0; i < A.size(); i ++) {
            int curr = sorted.get(i);
            int orig = A.get(i);
            if (curr != orig) {
                left = i;
                break;
            }
        }
        for (int i = A.size() - 1; i >= 0; i --) {
            int curr = sorted.get(i);
            int orig = A.get(i);
            if (curr != orig) {
                right = i;
                break;
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        if (left != -1 && right != -1) {
            result.add(left);
            result.add(right);
        } else {
            result.add(-1);
        }
        return result;
    }
}

思路2

       1  2  3  3  4  5   - sorted
A = [1, 3, 2, 3  4, 5]
min  1  2  2  3  4  5
max 1  3  3  3  4  5

顺着刚才的思路，我们要找sort完后左右两边第一个不一样的数，我们可以发现A1其实就是min array中第一个不等于自己本来位置的数，所以A1需要变到这个位置，A2就是max array中第一个不等于自己本来位置的数（从右往左），所以A2需要变到这个位置。

Solution2:

Time: O(n)
Space: O(n)

public class Solution {
    public ArrayList<Integer> subUnsort(ArrayList<Integer> A) {
        int n = A.size();
        int[] mins = new int[n];
        int[] maxs = new int[n];
        maxs[0] = A.get(0);
        for(int i = 1; i < n; i++) {
            maxs[i] = Math.max(A.get(i), maxs[i-1]);
        }
        mins[n-1] = A.get(n-1);
        for(int i = n - 2; i >= 0; i--) {
            mins[i] = Math.min(A.get(i), mins[i+1]);
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        int start = 0;
        while (start < n && mins[start] == A.get(start)) start++;
        int end = n - 1;
        while (end >= 0 && maxs[end] == A.get(end)) end--;
        if(start == n) result.add(new Integer(-1));
        else {
            result.add(new Integer(start));
            result.add(new Integer(end));
        }
        return result;
    }
}