Java O(n) with explanation


  • 0
    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            if(nums==null||nums.length==0) return 0;
            int start=-1, end=-1;
            int max=nums[0], min=nums[nums.length-1];
            //the final end must be the last number which is >some previouse number
            for(int i=1; i<nums.length; i++){
                if(nums[i]<max) end=i;
                else if(nums[i]>max) max=nums[i];
            }
            if(end==-1) return 0; //All numbers are in order
            //the final start must be the first number which is <some latter number
            for(int i=nums.length-2; i>=0; i--){
                if(nums[i]>min) start=i;
                else if(nums[i]<min) min=nums[i];
            }
            return end-start+1;
        }
    }
    

Log in to reply
 

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