Straightforward java O(n) time, O(n) space solution, 40ms passes all testcases


  • 0
    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int start=0;
            int end=0;
            int min=0;
            int max=0;
            //find the the discontinuous indexes of both sides
            for(int i=0;i<nums.length-1;i++)
            {
                
                
                if(nums[i]>nums[i+1])
                {
                    start=i;
                    break;
                }
            }
            
             for(int i=nums.length-1;i>0;i--)
            {
                if(nums[i]<nums[i-1])
                {
                    end=i;
                    break;
                }
            } 
           // find the max and min between start and end;  
             if(end>start)
    
             {
                     min=nums[start];
                     max=nums[end];
                 for(int i=start;i<=end;i++)
                 {
                     if(nums[i]>max)
                         max=nums[i];
                     if(nums[i]<min)
                         min=nums[i];
                 }
             }
            else return 0;
            // find the positions of previous max and min in continuous part
            for(int i=0;i<nums.length;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.