Java O(n) time O(1) space, beats 98%


  • 0
    K

    algorithm:

    from the left, go until nums[i + 1] is not greater than or equal to nums[i]
    store the value of i as "left"
    from the right, go until nums[i - 1] is not less than or equal to nums[i]
    store the value of i as "right"

    between left and right, find the minimum and maximum value
    then, starting from i = 0, find the index of the first value that is greater than the minimum
    store that index as start

    then, starting from i = length - 1, find the index of the first value that is less than the maximum
    store that index as end

    return end - start + 1

    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int left = -1;
            int right = -1;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            int start = 0;
            int end = 0;
            
            for (int i = 0; i < nums.length - 1; i ++) {
                if (nums[i + 1] < nums[i]) {
                    left = i;
                    break;
                }
            }
            
            if (left == -1) {
                return 0;
            }
            
            for (int i = nums.length - 1; i >= 1; i --) {
                if (nums[i - 1] > nums[i]) {
                    right = i;
                    break;
                }
            }
            
            for (int i = left; i <= right; i ++) {
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
            
            for (int i = 0; i < nums.length - 1; i ++) {
                if (nums[i] > min) {
                    start = i;
                    break;
                }
            }
            
            for (int i = nums.length - 1; i >= 0; i --) {
                if (nums[i] < max) {
                    end = i;
                    break;
                }
            }
            
            return end - start + 1;
        }
    }
    

Log in to reply
 

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