# Untitled

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()
```