# Find the smallest window in an array sorting which will make the entire array sorted

By | January 19, 2022

## Problem

Given an integer array `nums`, identify one continuous subarray that, if just this subarray is sorted in ascending order, the entire array will be sorted in ascending order.

Return and output the length of the shortest such subarray.

### Brute Force Approach

In this method, we employ a concept based on selection sort. We can select the items `nums``[i]` from the supplied `nums` array. We try to find the right location in the sorted array for each such element that is picked. To do this, we compare `nums``[i]` with each `nums``[j],` so that `i < j`` < n`. The length of the `nums` array is denoted by n. The time complexity of this approach is O(N2).

### Efficient Approach

Another basic concept is as follows. We can sort a duplicate of the supplied array nums, for example, using `nums2`. Then, by comparing the items of `nums` and `nums2`, we can identify which elements are mismatched on the left and right. The needed shortened unsorted subarray is then the subarray lying between them. The time complexity of this approach is O(NlogN).

### Python Programming

```def findUnsortedSubarray(nums):
if nums==sorted(nums) or len(nums)==1:
return 0
num1=sorted(nums)
N=len(nums)
ini=N
fin=0
for i,n in enumerate(nums):
if nums[i]!=num1[i]:
ini=min(ini,i)
fin=max(fin,i)
return fin-ini+1

l = [1, 2, 5, 4]
print(findUnsortedSubarray(l))```

Output

`2`

### More Efficient Approach

In this approach, we traverse the array twice. From left to right iteration, we find the latest index at which element has some previous element greater than it. For instance, if we have an `array: [1,10,4,15]`, then `4` is the latest element that has some element greater than it (that is 10) and that greater element should lie towards the left. We can conclude that our subarray will end at index 2 here (0-based indexing). Similarly, we can find the first element that has some element smaller than it and this smaller element lies towards the right. In the above example, 10 is that element (having 4 as a smaller element). Therefore, our final and initial indices are 1 and 2. The time complexity of this approach is O(N).

#### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
int findUnsortedSubarray(vector<int>& nums) {
int small=INT_MAX,large=INT_MIN;
int fin=-1;
int ini=-1;
int n=nums.size();
for(int i=0;i<n;i++){
if(large>nums[i]){
fin=i;  //update ending index of window

}
large=max(large, nums[i]);  //keep track of largest element

}
for(int i=n-1;i>=0;i--){
if(small<nums[i]){
ini=i;   //update initial index of window
}
small=min(small, nums[i]); //keep track of smallest element

}

if(fin==-1 && ini==-1) return 0;
return fin-ini+1;
}
int main(){
vector<int>v{1, 2, 5, 4};
cout<<findUnsortedSubarray(v);

}```

Output

`2`

### C Programming

```#include<stdio.h>
#define INT_MAX 1000000000;
#define INT_MIN -1000000000;
int max(int a, int b){
return a>=b?a:b;
}
int min(int a, int b){
return a>=b?b:a;
}

int findUnsortedSubarray(int* nums, int n){
int small=INT_MAX; int large=INT_MIN;
int fin=-1;
int ini=-1;
for(int i=0;i<n;i++){
if(large>nums[i]){
fin=i;  //update ending index of window

}
large=max(large, nums[i]);  //keep track of largest element

}
for(int i=n-1;i>=0;i--){
if(small<nums[i]){
ini=i;   //update initial index of window
}
small=min(small, nums[i]); //keep track of smallest element

}

if(fin==-1 && ini==-1) return 0;
return fin-ini+1;
}
void main(){
int a[] = {1, 2, 5, 4};
int n =  sizeof(a)/sizeof(a[0]);
printf("%d", findUnsortedSubarray(a, n));
}```

Output

`2`

### Python Programming

```def findUnsortedSubarray(nums):
# go from ini to fin, find rightmost index of our array
fin, large = 0, nums[0]
i = 1
while i < len(nums):
if nums[i] < large:
fin = i
else:
large = nums[i]
i += 1
if fin == 0:
return 0

# go from fin to ini, find the leftmost index
ini, small = len(nums)-1, nums[-1]
i = ini - 1
while i >= 0:
if nums[i] > small:
ini = i
else:
small = nums[i]
i -= 1

return fin - ini + 1

l = [1, 2, 5, 4]
print(findUnsortedSubarray(l))```

Output

```2
```

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.