Java O(n) Time O(1) Space


  • 93

    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;
    }
    

  • 8
    D

    initialize end = -2 is a smart move. we can always return end - beg + 1, no need to check if the array is already sorted.


  • 0
    K

    @compton_scatter highly appreciate ur solution, quite impressed.


  • 3
    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.


  • 10
    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.


  • 1

    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;
    }

  • 1
    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.


  • 1
    • Clone the array, sort the array.

    • Compare the sorted and origin array:

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

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

    Between them is the range.

          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;

  • 0
    W

    @yuxiangmusic That's right. If it's 1, 5, 7, 9. then if statement doesn't change end and beg. so we just add it to be ZERO. if it's [2, 6, 4, 8, 10, 9, 15], then end =5, beg=n-6=1.


  • 0
    X

    What an awesome solution!!!
    Who was training you?


  • 10
    S

    Awesome!

    Some explanations:

    endIdx = The most right element having greater elements on the left side.
    begIdx = The most left element having smaller elements on the right side.

    Prove it is effective:
    According to the definition, we can know that all elements on the right side of endIdx do not have greater elements on the left side and all elements on the left side of the begIdx do not have greater elements on the right side. Therefore, these two parts are good and we only need to sort the elements between begIdx and endIdx.

    Prove the bounds are tight:
    According to the definition, the two elements at begIdx and endIdx are "illegal", so the range to be sort should at least include these two elements.


  • 0

    @szlghl1 Nice explanation. Maybe add something like if A[i] has greater element to its left, then A[i] must be smaller to the max of 0..i-1. But again, I think your illustration overall is good and my suggestion only helps in a next to trivial way.


  • 0

    This is one of the kind of algorithms that appears simple on first sight but are actually ingenuity in disguise.


Log in to reply
 

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