Java O(n) Time O(1) Space


  • 57

    I use the variables beg and end to keep track of minimum subarray A[beg...end] which must be sorted for the entire array A to be sorted. If end < beg < 0 at the end of the for loop, then the array is already fully sorted.

    public int findUnsortedSubarray(int[] A) {
        int n = A.length, beg = -1, end = -2, min = A[n-1], max = A[0];
        for (int i=1;i<n;i++) {
          max = Math.max(max, A[i]);
          min = Math.min(min, A[n-1-i]);
          if (A[i] < max) end = i;
          if (A[n-1-i] > min) beg = n-1-i; 
        }
        return end - beg + 1;
    }
    

  • 2
    D

    initialize end = -2 is a smart move


  • 0
    K

    @compton_scatter highly appreciate ur solution, quite impressed.


  • 1
    K

    @compton_scatter Hello, buddy, I was quite confused that u can come up with such a nice solution, what`s ur thinking recipe ? Even after I read ur solution, imitate ur thinking and write the code out, I asked myself if I was remembering ur code, not ur study or thinking pattern. The ones who can solve the problems quickly, if it depends on how many similar questions they have resolved or they have set up good thinking pattern.


  • 3
    M

    Thanks for sharing, O(n) runtime, O(1) space, the best possible, thanks for sharing.
    The "end = -2" is smart, to make code more concise, when the entire array is aready sorted. You can use a "if" to check instead:

    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int len=nums.length;
            int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;
            int start=-1, end=-1;
            
            for(int i=0; i<len; i++){
                max = Math.max(max, nums[i]); //from left to right, search the current max
                min = Math.min(min, nums[len-i-1]);  //from right to left, search the current min 
                
                if(nums[i] < max)  
                    end = i;
                if(nums[len-i-1] > min)
                    start = len-i-1;
            }
            
            if(start==-1) //the entire array is already sorted
                return 0;
            
            return end-start+1;
        }
    }
    

  • 1
    Y

    @mycoy
    I'd like to point out an interesting fact that as long as you make sure end - beg + 1 == 0 then you can actually initialize them to anything, because if a valid beg can be found then it is guaranteed that valid end must exist as well.

    For example, if you do beg = 1000, end = 999 you would still get the correct result.


  • 0
    K

    @mycoy I have to say that the original post writer`s answer is simpler than urs. Indeed, end = -2 is a trick hard to think of. urs provide us a common solution to solve this problem, thanks for ur sharing.


  • 0
    T

    Very fantastic idea!! I update it to be more cleaner:)

    public int findUnsortedSubarray(int[] nums) {
        int start = -1, end = -2, max = nums[0], min = nums[nums.length-1];
        for(int index = 1; index < nums.length; index++){
            if(nums[nums.length - 1 - index]<=min) min = nums[nums.length - 1 - index];
            else start = nums.length - 1 - index;
            if(nums[index]>=max) max = nums[index];
            else end = index;
        }
        return end - start+1;
    }

  • 0
    B

    my O(n) solution with constant space

        public int findUnsortedSubarray(int[] nums) {
            if(nums == null){
                return 0;
            }
    
            int start = -1, end = -1;
            int max = nums[0];
            int min = Integer.MAX_VALUE;
            for(int i =1; i<nums.length; i++){
                if(nums[i] < nums[i-1] || max > nums[i]){
                    end = i;
    
                    max = Math.max(max, nums[i-1]);
                    min = Math.min(min, nums[i]);
                    if(start == -1){
                        start = i-1;
                    }
                }
            }
            
            if(start == -1){
                return 0;
            }
            for(int i=0; i<=start; i++){ //first number greater than min
                if(nums[i] > min){
                    start = i;
                    break;
                }
            }
            
            for(int i =nums.length -1; i>=end;i--){//first number less than max
                if(nums[i] < max){
                    end = i;
                    break;
                }
            }
            
            return start != -1 ? end - start + 1 : 0;
        }

  • 0
    S

    @Dongwei. @mycoy Wang as long as the initial end value is less than beg 1 && less than 1 will all be valid~ like: beg = 0,. end = -1


  • 0
    S

    @yuxiangmusic you are correct, the initial value of beg and end is only for the sorted input case, so like you said,. as long as end- beg+1 == 0 is fine!


  • 0
    D

    @Stephen The reason to initialize beg = -1 && end = -2 is to make these two values are not any index of the array, what you said is also correct.
    For my preferences, I would like to initialize beg = -1.


  • 0
    V

    @Dongwei.Wang said in Java O(n) Time O(1) Space:

    initialize end = -2 is a smart move

    there is no need to initialize end =-2,it is not the point of the solution


  • 1
    D

    @vanpersie32 I think the reason to initialize end = -2 is always return end - beg + 1, no need to check if the array is already sorted.


  • 0

    from left to right, find the first different char,
    from right to left, find the first different char.

          int[] b = a.clone();
          Arrays.sort(b);
          int s = 0, e = a.length - 1;
          while(s < a.length && a[s] == b[s]){
            s++;  
          }
          
          while(s < e && a[e] == b[e]){
            e--;  
          }  
          
          return e - s + 1;

Log in to reply
 

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