Java Solution, Sort.


  • 31
    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int n = nums.length;
            int[] temp = nums.clone();
            Arrays.sort(temp);
            
            int start = 0;
            while (start < n  && nums[start] == temp[start]) start++;
            
            int end = n - 1;
            while (end > start  && nums[end] == temp[end]) end--;
            
            return end - start + 1;
        }
    }
    

  • 0
    W

    @shawngao Thanks for the solution. These two lines can be replaced with int[] temp = nums.clone();

    int[] temp = new int[n];
    for (int i = 0; i < n; i++) temp[i] = nums[i];
    

  • 0

    @wai_ting That's right. Updated my post. Thanks!


  • 0

    Nice solution. With O(N) extra space and sorting time, much simpler algorithm.


  • 0
    C

    Not a optimal solution, as the Time complicity is O(N*logN) due to the sort. the best solution should be O(N)


  • 0
    S

    @shawngao test fails for input [1,2,3,4]
    for that need to add extra condition as if(start==end)return 0;


  • 0
    L

    Very simple algo. This was my thought process as well.


  • 1
    L

    I think we don't need two loops, we can do it in one loop like this.

    
        int start = -1;
        int end = -1;
        for(int i = 0; i < nums.length; i++) {
          if(nums[i] != copiedNums[i]) {
            if(start  == -1) {
              start = i;
            }
            end = i;
          }
        }
    

Log in to reply
 

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