Untitled

mail@pastecode.io avatar
unknown
python
3 years ago
2.6 kB
5
Indexable
Never
#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'findSubsequence' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def findSubsequence(arr):
    
    Array = arr
    N = len(Array)
    MAX_INT=1000000
    
        # To store the indices where 0, 1, 2,
    # 3 and 4 are present
    pos=[[] for i in range(5)]
 
    # To store if there exist a valid prefix
    # of sequence in array
    pref=[0 for i in range(5)]
 
    # Base Case
    if (Array[0] == 0):
        pref[0] = 1
        pos[0].append(0)
     
 
    ans = MAX_INT
 
    for i in range(N):
 
        # If current element is 0
        if (Array[i] == 0):
 
            # Update the count of 0s till now
            pref[0]+=1
 
            # Push the index of the new 0
            pos[0].append(i)
         
        else :
 
            # To check if previous element of the
            # given sequence is found till now
            if (pref[Array[i] - 1] > 0):
                pref[Array[i]]+=1
                pos[Array[i]].append(i)
 
                # If it is the end of sequence
                if (Array[i] == 4) :
                    end = i
                    start = i
 
                    # Iterate for other elements of the sequence
                    for j in range(3,-1,-1):
                        s = 0
                        e = len(pos[j]) - 1
                        temp = -1
 
                        # Binary Search to find closest occurrence
                        # less than equal to starting point
                        while (s <= e):
                            m = (s + e) // 2
                            if (pos[j][m] <= start) :
                                temp = pos[j][m]
                                s = m + 1
                             
                            else :
                                e = m - 1
                             
                         
 
                        # Update the starting point
                        start = temp
                     
 
                    ans = min(ans, end - start + 1)
                 
             
         
     
 
    return ans
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr_count = int(input().strip())

    arr = []

    for _ in range(arr_count):
        arr_item = int(input().strip())
        arr.append(arr_item)

    result = findSubsequence(arr)

    fptr.write('\n'.join(map(str, result)))
    fptr.write('\n')

    fptr.close()