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.
1function findUnsortedSubarray(nums) {
2 const sorted = [...nums].sort((a, b) => a - b);
3 let start = 0, end = nums.length - 1;
4 while (start < nums.length && nums[start] === sorted[start]) {
5 start++;
6 }
7 while (end > start && nums[end] === sorted[end]) {
8 end--;
9 }
10 return start < end ? end - start + 1 : 0;
11}
12
13// Example usage:
14const nums = [2, 6, 4, 8, 10, 9, 15];
15console.log(findUnsortedSubarray(nums)); // Output: 5JavaScript uses the spread operator to create a copy and sorts it. We detect differences from the start and end in parallel.
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.