Problem: Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.
Example:
Input: nums = [2,3,1,4,5] Output: 3 Explanation: You need to sort [2,3,1] in ascending order to make the whole array sorted in ascending order.
Approach: The intuition is that the correct position of the minimum element in the unsorted subarray is the required left boundary. Similarly, the correct position of the maximum element in the unsorted subarray is the required right boundary.
One way to achieve it is first we create a copy of the original array say sortedNums and then sort it. Now for every i = 0 to n - 1 whenever we find num[i] != sortedNums[i] first time we know that this is the minimum element which is not in correct order so we mark 'i' as the left boundary.
To get the right boundary, we could parse in reverse order i.e. i = n - 1 to 0 and whenever we find num[i] != sortedNums[i] first time we know that this is the maximum element which is not in correct order so we mark 'i' as the right boundary. Now we can return right - left + 1.
This approach will work but it will take O(nlogn) time for sorting. Let's try to do better; Can we find the min and max element of unsorted subarray without sorting? Once we find the min and max element, its easy to find the indexes where these min and max should be placed.
Let's see how to find the min number in the unsorted subarray. For every i = 1 to n - 1 whenever we find that nums[i] < nums[i - 1] that mean at 'i' unsorted subarray is started and now we can find the min of subarray nums[i...n-1] which is our minimum number.
Similarly, to get the max number we can have a loop from i = n - 2 to 0 and whenever we find nums[i] > nums[i + 1] that means we get the end of unsorted subarray. Now we can find the max of subarray nums[0...i] and which will tell us the maximum number of the unsorted subarray.
Now we just traverse the array from i = 0 to n - 1 and whenever we see that nums[i] > min then we know that this is the right position for min and hence 'i' is our left boundary. Similarly we traverse the array in reverse order i.e. j = n - 1 to 0 and whenever we find that nums[j] < max then we can say 'j' is our right boundary. Now we can return right - left + 1.
That's all!
Implementation in C#:
Approach 1: With Sorting:
public int FindUnsortedSubarray(int[] nums)
{
int[] sortedNums = (int[]) nums.Clone();
Array.Sort(sortedNums);
int left = -1, right = 0;
for (int i = 0; i < nums.Length; ++i)
{
if (nums[i] != sortedNums[i])
{
left = i;
break;
}
}
// Already sorted
if (left == -1)
{
return 0;
}
for (int i = nums.Length - 1; i >= 0; --i)
{
if (nums[i] != sortedNums[i])
{
right = i;
break;
}
}
return right - left + 1;
}
Approach 2: Without Sorting:
public int FindUnsortedSubarray(int[] nums)
{
int min = int.MaxValue, max = int.MinValue;
bool isSorted = true;
int len = nums.Length;
for (int i = 1; i < len; ++i)
{
if (nums[i] < nums[i - 1])
{
isSorted = false;
}
if (!isSorted)
{
min = Math.Min(min, nums[i]);
}
}
if (isSorted)
{
return 0;
}
isSorted = true;
for (int i = len - 2; i >= 0; --i)
{
if (nums[i] > nums[i + 1])
{
isSorted = false;
}
if (!isSorted)
{
max = Math.Max(max, nums[i]);
}
}
int left = 0, right = len - 1;
for (; left < len; ++left)
{
if (nums[left] > min)
{
break;
}
}
for (; right >= 0; --right)
{
if (nums[right] < max)
{
break;
}
}
return right - left + 1;
}
Complexity: Approach 1: O(nlogn), Approach 2: O(n)
No comments:
Post a Comment