Find the range of shortest subarray which when removed will make the remaining elements in the array sorted?
Ex:
[1, 2, 3, 99, 4, 2, 3, 5]
Ans: [3, 5] - { 99, 4, 2 } which when removed will make array { 1, 2, 3, 3, 5} which is sorted.
ii) [1, 2, 3, 4 , 5]
Ans: []
iii) [5, 4, 3, 2 ,1]
Ans: [0, 3]
But, [1, 4] is also a valid answer.
Note: It is slightly different from https://leetcode.com/problems/shortest-unsorted-continuous-subarray/.
I found it really difficult in the interview to get this done in 20 mins. I was able to give a brute force solution of order O(n3). But, Is there an elegant and optimized way to do this ?
@gerrob, you are awesome man. you solution was spot on.
Added few comments, refactored for some edge cases. I still think it is hard to cover all these edge case in the interview.
public static int FindShortestUnsortedContiguousSequeuence(int[] arr)
{
if (arr.Length <= 1)
return 0;
int left = 0, right = arr.Length - 1;
//Find the first number which voilates the sorted order from right to left
while (right > 0 && arr[right - 1] <= arr[right])
right--;
//The whole array is sorted in ascending order
if (right == -1)
return 0;
//If all the elements from [0 ... right - 1] is greater than arr[right], then 'right' would be the length of the subarray to be removed
//Ex: [99,100,11,12,13,14] - 'right' would be pointing to index 2 here which is length of the subarray to be removed.
//This could be an answer in this case but not on all cases.
//What if the length of the left side [0 ... right - 1] is sorted and has a length greater than right side.
//Ex: [51,52,53,54,55,56,57,58,1,2,3] - 'right' would be pointing to index 8 here.
//But we have a sorted subarray of length 8 [0 .. 7] on the left, so left side needs to be explored
//We will initialize the answer to right and take a minimum if we get a better result
int ans = right;
//Find the first number from the left which violates the sort order.
while (left < arr.Length - 1 && arr[left] <= arr[left + 1])
{
//In this case [1, 2, 3, 4, 5, 12, 13, 13, 13, 91, 92 , 12, 13, 14, 15, 16, 17, 18, 19, 20]
// answer at this point would of length 5 between [6 ... 10] - { 13, 13, 13, 91, 92}
// But the actual answer of Length 3 [9 .. 11] - { 91, 92, 12 }
// --------------
// [1, 2, 3, 4, 5, 12, 13, 13, 13, | 91, 92, 12 | , 13, 14, 15, 16, 17, 18, 19, 20]
//This while loop handles this case
while (right < arr.Length && (right <= left || arr[right] < arr[left]))
right++;
// l l l r
//[ 1,2,3, 55,56,58, 4,5,6,7,8,9,10 ]
if (right < arr.Length && arr[left] <= arr[right])
ans = Math.Min(ans, right - left - 1);
left++;
}
//Ex: [51,52,53,54,55,56,57,58,1,2,3] where the left subarray [0 ... left] is sorted and has more elements than right side. So the answer needs to be updated.
ans = Math.Min(ans, arr.Length - left - 1);
return ans;
}Without comments
public static int FindShortestUnsortedContiguousSequeuence(int[] arr)
{
if (arr.Length <= 1)
return 0;
int left = 0, right = arr.Length - 1;
while (right > 0 && arr[right - 1] <= arr[right])
right--;
if (right == -1)
return 0;
int ans = right;
while (left < arr.Length - 1 && arr[left] <= arr[left + 1])
{
while (right < arr.Length && (right <= left || arr[right] < arr[left]))
right++;
if (right < arr.Length && arr[left] <= arr[right])
ans = Math.Min(ans, right - left - 1);
left++;
}
ans = Math.Min(ans, arr.Length - left - 1);
return ans;
}If you still find some edge cases, please suggest. Thanks.