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


  • 0
    M

    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;
    

Log in to reply
 

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