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))
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/ ):