# O(n) time, O(1) space Java Solution with Comments

#1
``````public ArrayList<Integer> subUnsort(ArrayList<Integer> A) {
ArrayList<Integer> result = new ArrayList<>();

// Array of size 0 or 1 is always sorted.
if (A.size() <= 1) {
return result;
}

int n = A.size();
int i = 0, j = n - 1;

// Get the first index i where the next element is smaller than current index.
while(i+1 < n && A.get(i+1) >= A.get(i)) {
i++;
}

// If i is the last element, then the array is sorted.
if (i == n - 1) {
return result;
}

// Get the first index j where the previous element is larger than current element.
while(A.get(j) >= A.get(j-1)) {
j--;
}

// Find min and max between [i, j]
int min = A.get(i), max = A.get(i); // Just initialized
for(int p = i+1; p <= j; p++) {
if(A.get(p) < min) {
min = A.get(p);
} else if(A.get(p) > max) {
max = A.get(p);
}
}

// Move i back to the point where ith element is <= min
while(i >=0 && A.get(i) > min){
i--;
}

// Move j forward where jth element is >= max
while(j < n && A.get(j) < max) {
j++;
}

// Result is the range from i+1, j-1