## Tuesday, May 17, 2022

### Easy_Question16 : Shortest Unsorted Continuous Subarray

Given an integer array nums, 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 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending orderto make the whole array sorted in ascending order.
Example 2:
Input: nums = [1,2,3,4]
Output: 0
Example 3:
Input: nums = [1]
Output: 0

Constraints:
1 <= nums.length <= 104
-105 <= nums[i] <= 105


#### Approach 1 : Brute Force

public class Solution {
public int findUnsortedSubarray(int[] nums) {
int l = nums.length, r = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
r = Math.max(r, j);
l = Math.min(l, i);
}
}
}
return r - l < 0 ? 0 : r - l + 1;
}
}

Complexity Analysis

• Time complexity : $O(n^2)$. Two nested loops are there.

• Space complexity : $O(1)$. Constant space is used.

#### Approach 2: Using Sorting

Algorithm

public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] snums = nums.clone();
Arrays.sort(snums);
int start = snums.length, end = 0;
for (int i = 0; i < snums.length; i++) {
if (snums[i] != nums[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return (end - start >= 0 ? end - start + 1 : 0);
}
}

Complexity Analysis

• Time complexity : $O(n\log n)$. Sorting takes $n\log n$ time.

• Space complexity : $O(n)$. We are making copy of original array.

#### Approach 3: Without Using Extra Space

Algorithm

public class Solution {
public int findUnsortedSubarray(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
boolean flag = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1])
flag = true;
if (flag)
min = Math.min(min, nums[i]);
}
flag = false;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1])
flag = true;
if (flag)
max = Math.max(max, nums[i]);
}
int l, r;
for (l = 0; l < nums.length; l++) {
if (min < nums[l])
break;
}
for (r = nums.length - 1; r >= 0; r--) {
if (max > nums[r])
break;
}
return r - l < 0 ? 0 : r - l + 1;
}
}Complexity Analysis
Time complexity : O(n) Four O(n)O(n) loops are used.
Space complexity : O(1). Constant space is used.

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS