Discussion on Lily's Homework Challenge

c_m_s_gan 2 years ago+ 0 comments

Correction:

def lilysHomework(a):

    m = {}
    a_original = a.copy()

    for i in range(len(a)):
        m[a[i]] = i 
        
    sorted_a = sorted(a)
    ret = 0
    
    for i in range(len(a)):
        if a[i] != sorted_a[i]:
            ret +=1
            
            ind_to_swap = m[ sorted_a[i] ]
            m[ a[i] ] = m[ sorted_a[i]]
            a[i],a[ind_to_swap] = sorted_a[i],a[i]

    ret2 = 0

    m = {}
    a = a_original.copy()

    for i in range(len(a)):
        m[a[i]] = i 

    for i in range(len(a)):
        if a[i] != sorted_a[len(a)-1-i]:
            ret2 +=1
            
            ind_to_swap = m[ sorted_a[len(a)-1-i] ]
            m[ a[i] ] = m[ sorted_a[len(a)-1-i]]
            a[i],a[ind_to_swap] = sorted_a[len(a)-1-i],a[i]



    return min(ret,ret2)

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

def lilysHomework(arr):

    arr_original = arr.copy()
    
    b = [None]*(max(arr)+1)
    l = len(arr)

    k = (max(arr))
    hist = (k+1)*[0] #indices runs from 0 to max(array) inclusive

    for i in arr:
        hist[i] = 1    #Initial frequency array, jth value of count is the frequency of number j

    
    cumfreq = (k+1)*[0]
    cumfreq[0] = hist[0]

    invcumfreq = {}

    for j in range(1,k+1):
        cumfreq[j] += cumfreq[j-1] + hist[j]

        if not(cumfreq[j] in invcumfreq):
            invcumfreq[cumfreq[j]] = j

    ## Create an array to get the inverse cumulative frequencies array:

    
    

    counter1 = 0

    for j,v in enumerate(arr_original):
        b[v] = j
        
    for j in range(l):
        if cumfreq[arr[j]] - 1 != j:
            old = arr[j]  # old arr[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 += 1
        
        else:
            continue
    
    arr = arr_original.copy()

    ##Reset the b-array of indices!!

    for j,v in enumerate(arr_original):
        b[v] = j

    counter2 = 0
        
    for j in range(0,l):
        if cumfreq[arr[j]] != l - j:
            old = arr[j]  # old arr[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 += 1
        
        else:
            continue
    

    return counter1 #(min(counter1,counter2))