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.
Hahaha thanks for the tip; couldn't believe that assigning the lengths and the "result.append" method to variables actually sped up the algorithm significantly.
I had a variant with nested functions earlier (merge nested in mergesort, mergesort nested in countInversions) that timed out on more than half of the cases.
So essentially my solution is virtually similar to yours; anyone with a better way apart from tweaking the mergesort boilerplate code to keep track of the number of occurrences?
defmerge(left,right):counter=0result=[]#finalresultarray,thatisanemptyarray#create two indices and initialize with 0i,j=0,0ra=result.appendlenl=len(left)lenr=len(right)# Till this condition is true, keep on appending elements into resultant arraywhile(i<lenl)and(j<lenr):ifleft[i]<=right[j]:ra(left[i])#appendithelementofleftintoresultantarrayi+=1else:ra(right[j])#appendjthelementofrightintoresultantarrayj+=1counter+=lenl-i#COUNTHERE!# it is basically specifies that if any element is remaining in the left array from -# ith to the last index so that it should appended into the resultant array. And similar -# to the right array.result+=left[i:]result+=right[j:]returnresult,counter# Definition for merge sort# this takes an input listdefmergesort(lst):if(len(lst)<=1):#thismeansthatthelistisalreadysorted.returnlst,0mid=(len(lst)//2)# Define definition for merge which basically takes two arrays i.e., the left and right part# left array will be mergesort applied over the list from starting index # till the mid indexleft,counter0=mergesort(lst[:mid])# right array will be mergesort applied recursively over the list from mid index# till the last index right,counter1=mergesort(lst[mid:])result,counter2=merge(left,right)returnresult,counter2+counter0+counter1defcountInversions(arr):#Idea: Count the number of transpositions needed when you apply the mergesort to arr.final,counter=mergesort(arr)returncounter
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Hahaha thanks for the tip; couldn't believe that assigning the lengths and the "result.append" method to variables actually sped up the algorithm significantly.
I had a variant with nested functions earlier (merge nested in mergesort, mergesort nested in countInversions) that timed out on more than half of the cases.
So essentially my solution is virtually similar to yours; anyone with a better way apart from tweaking the mergesort boilerplate code to keep track of the number of occurrences?