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.
Can someone please tell me why my initial attempt timeouts? Here, a histogram array was used to construct a cumulative frequency array of the elements, which was then used as the keys for the correct positions of the numbers in the original array (similar to the Minimum Swaps 2 problem at https://www.hackerrank.com/challenges/minimum-swaps-2/ ):
deflilysHomework(arr):arr_original=arr.copy()b=[None]*(max(arr)+1)l=len(arr)k=(max(arr))hist=(k+1)*[0]#indicesrunsfrom0tomax(array)inclusiveforiinarr:hist[i]=1#Initialfrequencyarray,jthvalueofcountisthefrequencyofnumberjcumfreq=(k+1)*[0]cumfreq[0]=hist[0]invcumfreq={}forjinrange(1,k+1):cumfreq[j]+=cumfreq[j-1]+hist[j]ifnot(cumfreq[j]ininvcumfreq):invcumfreq[cumfreq[j]]=j## Create an array to get the inverse cumulative frequencies array:counter1=0forj,vinenumerate(arr_original):b[v]=jforjinrange(l):ifcumfreq[arr[j]]-1!=j:old=arr[j]#oldarr[j]arr[j],arr[b[invcumfreq[j+1]]]=arr[b[invcumfreq[j+1]]],arr[j]#arr[j],arr[b[cumfreq.index(j+1)]]=arr[b[cumfreq.index(j+1)]],arr[j]b[old],b[arr[j]]=b[arr[j]],b[old]counter1+=1else:continuearr=arr_original.copy()##Reset the b-array of indices!!forj,vinenumerate(arr_original):b[v]=jcounter2=0forjinrange(0,l):ifcumfreq[arr[j]]!=l-j:old=arr[j]#oldarr[j]arr[j],arr[b[invcumfreq[l-j]]]=arr[b[invcumfreq[l-j]]],arr[j]#arr[j], arr[b[revfreq.index(l-j)]] = arr[b[revfreq.index(l-j)]], arr[j] b[old],b[arr[j]]=b[arr[j]],b[old]counter2+=1else:continuereturncounter1#(min(counter1,counter2))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
Correction:
Tried and tested - passes all cases.
Can someone please tell me why my initial attempt timeouts? Here, a histogram array was used to construct a cumulative frequency array of the elements, which was then used as the keys for the correct positions of the numbers in the original array (similar to the Minimum Swaps 2 problem at https://www.hackerrank.com/challenges/minimum-swaps-2/ ):