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.
public class Solution {
public int[] subUnsort(int[] nums) {
if (nums.length == 0 || nums.length == 1)
return new int[] { -1 };
int max = Integer.MIN_VALUE;
int end = -2;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
if (nums[i] < max)
end = i;
}
int min = Integer.MAX_VALUE;
int start = -1;
for (int i = nums.length - 1; i >= 0; i--) {
min = Math.min(min, nums[i]);
if (nums[i] > min)
start = i;
}
if (end - start + 1 == 0)
return new int[] { -1 };
return new int[] { start, end };
}
}
Last updated