Maximum Unsorted Subarray Asked in: Amazon Microsoft

 You are given an array (zero-indexed) of N non-negative integers, A0, A1 ,…, AN-1.

Find the minimum sub-array AlAl+1,…, Ar so if we sort(in ascending order) that sub-array, then the whole array should get sorted.
If A is already sorted, output -1.

Example :

Input 1:

A = [1, 3, 2, 4, 5]

Return: [1, 2]

Input 2:

A = [1, 2, 3, 4, 5]

Return: [-1]

In the above example(Input 1), if we sort the subarray A1A2, then whole array A should get sorted.ut

Solution:
class Solution:
    # @param A : list of integers
    # @return a list of integers
    def subUnsort(self, A):
        s_a=sorted(A)
        if A==s_a:
            return [-1]
        l=len(A)
        minI=-1
        maxI=l
        f1=True
        f2=True
        for i in range(l):
            if A[i]!=s_a[i] and i>minI and f1==True:
                minI=i
                f1=False
            if A[l-i-1]!=s_a[l-i-1] and l-1-i<maxI and f2==True:
                maxI=l-i-1
                f2=False
            if f1==False and f2==False:
                break
        return [minI,maxI]
            
Screenshot:








Comments

Popular posts from this blog

Trouble with the Number System

Residue Arithmetic

Perfect Peak of Array