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]
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:
- Python Program to Find the Factors of Number
- How many Centimeters in a Foot through Python?
- Python Examples
- How to Find Square Root in Python?
- C Program to Design Love Calculator
- Rectangle & Pyramids Pattern in C++
- C Program to Convert Feet into Inches
- Python Program to Print Hello world!
- C Program to Extract a Portion of String
- Linear Search in Python and C++
Leave a Comment on this Post