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

Posted in

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

Vinay Khatri
Last updated on December 10, 2024

    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:

    Leave a Comment on this Post

    0 Comments