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.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

  • c_m_s_gan
     + 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))