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);
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
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 