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.
1import java.util.Arrays;
2
3public class Solution {
4 public int findUnsortedSubarray(int[] nums) {
5 int[] sorted = nums.clone();
6 Arrays.sort(sorted);
7 int start = 0, end = nums.length - 1;
8 while (start < nums.length && nums[start] == sorted[start]) {
9 start++;
10 }
11 while (end > start && nums[end] == sorted[end]) {
12 end--;
13 }
14 return start < end ? end - start + 1 : 0;
15 }
16 public static void main(String[] args) {
17 Solution solution = new Solution();
18 int[] nums = {2, 6, 4, 8, 10, 9, 15};
19 System.out.println(solution.findUnsortedSubarray(nums)); // Output: 5
20 }
21}The Java solution functions similarly by creating a sorted copy, comparing each element with the original, and returning the range of mismatch.
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.