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

Lily's Homework

  • purbanski + 8 comments

    Above described solution in python:

    def solution(a):

    m = {}
    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]
    return ret

raw_input()
a = [int(i) for i in raw_input().split(' ')]

asc=solution(list(a))
desc=solution(list(reversed(a)))
print min(asc,desc)
    • jason_dam + 0 comments

      Thanks. Creating map was the key to get past those time outs.

    • rahul_jhun2wala + 2 comments

      Thanks for the explanation and the code but I have a concern. How does the reverse part work? You are reversing the list and then calling the sort function which will again sort it in ascending order. So ultimately you are checking swaps in just one direction. Please share your views.

      • bfletch + 1 comment

        The key appears to be that the map is created prior to the sorting, so it indeed is different for the two passes and results in the swaps being done in a different order.

        Specifically i in the first for loop is different for the two passes.

        • barnwalnikita1 + 3 comments

          i didn't get your explanation of reverse work.can you please explain me in brief manner?

          • bfletch + 0 comments

            If I understand your question, you are asking why the need to run the algorithm twice, once forward and once in reverse.

            The reason for the need to check the reverse case is in the definition of the problem. The requirements are that the array is sorted such the sum of the differences between each two consecutive numbers is minimized. There are two ways to acheive that goal -- ascending and descending sorting the list. The descending sort is the "reverse" in this case.

          • madhazelnut + 0 comments

            What he's effectively doing (albeit a little indirectly) is first comparing the input array with an asc-sorted reference, then with a desc-sorted reference and taking the smallest number of swaps of the two. That's how I did it.

          • srivastavaharsh1 + 0 comments

            To solve it take care of the descending ones too. A counter case to show we also have to take the descending one. Suppose if the array is-: 3 4 2 5 1 then the output should be 2. 5 4 2 3 1(swap 5 and 3) 5 4 3 2 1(swap 2 and 3) Hence the answer will be 2.

      • srivastavaharsh1 + 0 comments

        To solve it take care of the descending ones too. A counter case to show we also have to take the descending one. Suppose if the array is-: 3 4 2 5 1 then the output should be 2. 5 4 2 3 1(swap 5 and 3) 5 4 3 2 1(swap 2 and 3) Hence the answer will be 2.

    • seanexplode + 1 comment

      This is my code in python3.

      I failed to pass TC #1. What am I doing wrong here?

      def homework(n, arr):

    pos = dict()
    for i, num in enumerate(arr):
        pos[num] = i

    cnt = 0
    sorted_arr = sorted(arr)

    for i in range(len(arr)):
        if arr[i] != sorted_arr[i]:
            cnt += 1

            new_idx = pos[sorted_arr[i]]
            pos[arr[i]] = new_idx
            arr[i], arr[new_idx] = arr[new_idx], arr[i]

    return cnt


n = int(input().strip())
arr = list(map(int, input().strip().split()))

asc = homework(n, arr)
desc = homework(n, list(reversed(arr)))
print(min(asc, desc))
      • briceparent + 1 comment

        I had the same issue, even though my solution wasn't the same. It was caused by the fact that I was calling my solving function with arr directly instead of a copy of it. As in the function itself, arr is modified, the second call wasn't made using initial data but using modified data.

        asc = homework(n, list(arr))  # -> works

        also, I like the syntax:

        asc = solve(s, ar[::])
desc = solve(s, ar[::-1])
        • seanexplode + 0 comments

          Thanks a lot!

    • 19998sachinyadav + 1 comment

      Thanks. Creating map was the key to get past those time outs.

      • zhuanzhl + 0 comments

        nice pun

    • matt_murdock + 0 comments
      a[i],a[ind_to_swap] = sorted_a[i],a[i]

      can you explain this piece of code

    • skvit001 + 0 comments
      [deleted]
    • abhijeetgholap01 + 1 comment

      I see that you're comparing elements that are out of place and incrementing number of swaps (ret) value. But that is not neccessarily, number of minimum of swaps required.

      for example, array1: 2 5 3 1 array2: 1 2 3 5

      have 3 elements out of place. but minimum number of swaps required are 2. I would appreciate you can help me understand the algorithm.

      Thanks

      • LordGameleo + 0 comments

        Check it for reverse array1: 1 3 5 2 - it require two swaps. We are only taking min of ascending and descending.

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