Leetcode 581

Shortest Unsorted Continuous Subarray

Head on over here to try the problem for yourself.

I solved this problem using a two-pointer method.

Algorithm

The goal is to find the points where the array becomes unsorted. We use two loops, one to find the end of the unsorted sub-array and another to find the start of the unsorted sub-array. start = end = -1 as a way to check if they were updated or not during the loops. If they were not, then array is sorted and we return 0. Else we return end - start + 1.

Code

pbulic int findUnsortedSubarray(int[] nums) {
  int start = -1;
  int end = -1;

  int prev = 0;
  //finding end
  for(int i = 0; i < nums.length - 1; i++) {
    // try to find the index of next 
    // smallest number from prev
    if(nums[i] < nums[prev]) end = i;
    else prev = i;
  }

  int prev = nums.length - 1;
  //finding start
  for(int i = nums.length - 1; i >= 0; i--) {
    // try to find the index of nex
    // biggest number from prev
    if(nums[i] > nums[prev]) start = i;
    else prev = i;
  }

  return (start < 0 && end < 0) ? 0 : end - start + 1;
}

Testcases

[1,3,2,2,2]
start = 1
end = 4

An odd testcase that shows the strage loop working. In this case, the whole right side of the array is unsorted. For finding end, we would have the following run:

Finding start happens simlarly and we get a good result.