We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My first solution was to enumerate all the indexes for all the items in the array in a map of item : list of indexes, and the in same loop start checking for middle in the map, for for each index of the middle check for first such that first < middle. This is a solution but has a complexity of n^2 in the worst case scenario, so a four of test cases failed.
Then I saw I could add add an optimization for r=1, when we add all the combinations for item nC3. After adding this optimization, still two testcases failed.
This final solution works in O(n), and whjat we do is, instad of making triplets with last element as the focus, we make triplets with middle as the focus. We first calculate the frequncies of all disctinct numbers. Then we iterate but taking the current item as the middle. Then we try to form a triplet from the frequency_map of items we have not yet seen for the last item of the triplet, and from the frequency map of items we have already seen for the first item of the triplet. Add new found triplets (frequency of first * 1 * frequency of last) , and mark current item as seen by adding it to the seen frequency map. By using two maps for find last and first, we get better time complexity as we don't have to do the i < j < k check in the same map.
#!/bin/python3importmathimportosimportrandomimportreimportsys# Complete the countTriplets function below.defcountTriplets(arr,r):triplets=0.0# calculate frequencies for every itemitem_frequency_map={}foriteminarr:item_frequency_map[item]=item_frequency_map.get(item,0)+1ifr==1:foriteminitem_frequency_map:# for each different itemfrequency=item_frequency_map[item]# combination formaula for nC3triplets+=(frequency*(frequency-1)*(frequency-2))/6else:item_frequency_map_seen={}foriteminarr:# marking current item as takenitem_frequency_map[item]=item_frequency_map.get(item,0)-1ifitem%r==0:# use this item as middle of the tripletmiddle=item# find first of the triplet, item / rfirst=round(middle/r)# check in lower indexes, in map of already seen elementsfirst_frequency=item_frequency_map_seen.get(first,0)# find last of the triplet, item * rlast=round(middle*r)# check in higher indexes, in map of not seen elementslast_frequency=item_frequency_map.get(last,0)# print("new triplets for triplet (%s,%s,%s) are %s * %s" %(first,middle, last, first_frequency, last_frequency))# add possible cobinations seen this this item as middletriplets+=first_frequency*last_frequency# mark item as seenitem_frequency_map_seen[item]=item_frequency_map_seen.get(item,0)+1returnint(triplets)if__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')nr=input().rstrip().split()n=int(nr[0])r=int(nr[1])arr=list(map(int,input().rstrip().split()))ans=countTriplets(arr,r)fptr.write(str(ans)+'\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Count Triplets
You are viewing a single comment's thread. Return to all comments →
My first solution was to enumerate all the indexes for all the items in the array in a map of item : list of indexes, and the in same loop start checking for middle in the map, for for each index of the middle check for first such that first < middle. This is a solution but has a complexity of n^2 in the worst case scenario, so a four of test cases failed. Then I saw I could add add an optimization for r=1, when we add all the combinations for item nC3. After adding this optimization, still two testcases failed.
This final solution works in O(n), and whjat we do is, instad of making triplets with last element as the focus, we make triplets with middle as the focus. We first calculate the frequncies of all disctinct numbers. Then we iterate but taking the current item as the middle. Then we try to form a triplet from the frequency_map of items we have not yet seen for the last item of the triplet, and from the frequency map of items we have already seen for the first item of the triplet. Add new found triplets (frequency of first * 1 * frequency of last) , and mark current item as seen by adding it to the seen frequency map. By using two maps for find last and first, we get better time complexity as we don't have to do the i < j < k check in the same map.