Queries for number of distinct elements from a given index till last index in an array | Python implementation of the approach ; Function to perform queries to find number of distinct elements from a given index till last index in an array ; Check if current element already visited or not ; If not visited store current counter and increment it and mark check as 1 ; Otherwise if visited simply store current counter ; Perform queries ; Driver code
MAX = 100001 ; NEW_LINE def find_distinct ( a , n , q , queries ) : NEW_LINE INDENT check = [ 0 ] * MAX ; NEW_LINE idx = [ 0 ] * MAX ; NEW_LINE cnt = 1 ; NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( check [ a [ i ] ] == 0 ) : NEW_LINE INDENT idx [ i ] = cnt ; NEW_LINE check [ a [ i ] ] = 1 ; NEW_LINE cnt += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT idx [ i ] = cnt - 1 ; NEW_LINE DEDENT DEDENT for i in range ( 0 , q ) : NEW_LINE INDENT m = queries [ i ] ; NEW_LINE print ( idx [ m ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT a = [ 1 , 2 , 3 , 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE n = len ( a ) ; NEW_LINE queries = [ 0 , 3 , 5 , 7 ] ; NEW_LINE q = len ( queries ) ; NEW_LINE find_distinct ( a , n , q , queries ) ; NEW_LINE