Java Sorting Solution - Find left most and right most mismatch


  • 1

    Basically the idea is to compare the given array to it's sorted version, and find out the left most mismatch, and the right most mismatch.

        public int findUnsortedSubarray(int[] nums) {
            int result  = 0;
            int[] copy = Arrays.copyOf(nums, nums.length);
            Arrays.sort(nums);
            int l = 0, r = copy.length - 1;
            while(l < r) {
                if(copy[l] == nums[l]) l++;
                if(copy[r] == nums[r]) r--;
                if(copy[l] != nums[l] && copy[r] != nums[r]) break;
            }
            result = r - l + 1;
            if(l == r) result = 0;
            return result;
        }
    

  • 0
    S

    @jaqenhgar
    shorter writing style for same algorithm

    public int findUnsortedSubarray(int[] nums) {
            int [] copy = nums.clone();
            Arrays.sort(copy);
            int i = 0, j = nums.length-1;
            while(i<nums.length && copy[i]==nums[i]) i++;
            while(j>i && copy[j]==nums[j]) j--;
            return j-i+1;
        }
    

Log in to reply
 

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