Sponsored
Sponsored
We can sort a copy of the array and compare it with the original array to determine the boundaries of the subarray that needs to be sorted.
Sort the array and compare with the original array from the start and end to find the first and last mismatch. These mismatches will give the boundaries of the subarray.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing a copy of the array.
1def findUnsortedSubarray(nums):
2 sorted_nums = sorted(nums)
3 start, end = 0, len(nums) - 1
4 while start < len(nums) and nums[start] == sorted_nums[start]:
5 start += 1
6 while end > start and nums[end] == sorted_nums[end]:
7 end -= 1
8 return end - start + 1 if start < end else 0
9
10# Example usage
11nums = [2, 6, 4, 8, 10, 9, 15]
12print(findUnsortedSubarray(nums)) # Output: 5In Python, sorted copies the list and sorts it. We iterate from the start and end to find where the numbers differ and calculate the length of that interval.
In this approach, we aim to find the shortest unsorted subarray by utilizing two passes to find the minimum and maximum deviations from the sorted order.
The range between these two boundaries produces the result.
Time Complexity: O(n) as it processes the array twice.
Space Complexity: O(1) since no additional space is used apart from basic variables.
The idea is to use two scans of the array to find maximum and minimum deviation points. The logic helps in computing boundaries by tracking the range that is unsorted and quickly determines the shortest unsorted subarray.