# Java | O(n) solution | Easy to understand | No Sorting

• So the algorithm goes like this :

1. left = 0; right = nums.length - 1;
2. Find the left index where the 1st discrepancy occurs i.e. nums[left] >= nums[left + 1] && nums[left] >= nums[right]
3. Find the right index where the 1st discrepancy occurs i.e. nums[right] <= nums[right - 1] && nums[right] <= nums[left]
4. Now find the minimum and the maximum element in the subarray [left, right];
5. new_left_index = 0; new_right_index = nums.length - 1;
6. for (0..left) if (nums[new_left_index] <= min, then new_left_index++
7. for (len-1 .. right) if (nums[new_right_index] >= max) new_right_index--;
8. return new_right_index - new_left_index + 1;

Below is the code

``````public int findUnsortedSubarray(int[] nums) {

int left = 0;
int right = nums.length - 1;

while (left < right && nums[left] <= nums[left + 1] && nums[left] <= nums[right]) {
left++;
}

while (left < right && nums[right] >= nums[right - 1] && nums[right] >= nums[left]) {
right--;
}

// By this time we have got our first discrepancy at left index and at right index
// Now let us find the minimum and max element between left to right

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

if (left == right) {
return 0;
} else {
for (int i = left; i <= right; i++) {
min = nums[i] < min ? nums[i] : min;
max = nums[i] > max ? nums[i] : max;
}
}

//System.out.println("left=" + left + " : right=" + right);

// Now the left index is the index where the element is greater than the min
int left_index = 0;
int right_index = nums.length - 1;

while (nums[left_index] <= min) {
left_index++;
}

while (nums[right_index] >= max) {
right_index--;
}

//System.out.println("left_index=" + left_index + " : right_index=" + right_index);
return right_index - left_index + 1;
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.