Loading...

Sort 61 Discussions, By:

  • PU
    purbanski + 15 comments

    I've done it :) Passing all test :) My approach is:

    Prep stage:

    1. create map with:
      • keys : values from input list,
      • values : indexes of values from input list,
    2. make a copy of sorted input list

    Algo stage:

    Iterate through input list, and compare current value (lets call it cv) against value from sorted list (lets call it scv). If it is diffrent:

    • increment number of swaps
    • get index of the scv from map - map[scv],
    • in input list swap cv with scv,
    • update map[cv]=map[scv] (map[scv] does not need to be updated as we are not going to use it any more)

    Then you need to execute it on input list and reversed input list - the smaller return value - is the answer.

    Time complexity is equal to sort time complexity (usually O(n logn) ). Space O(n)

    • PU
      purbanski + 6 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)
      
      • JD
        jason_dam + 0 comments

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

      • RJ
        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.

          • VB
            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.

            • HS
              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.

        • HS
          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.

      • S
        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))
        
        • BP
          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])
          
          • S
            seanexplode + 0 comments

            Thanks a lot!

      • SY
        19998sachinyadav + 0 comments

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

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

        can you explain this piece of code

      • SK
        skvit001 + 0 comments
        [deleted]
    • AD
      anshumaan_dash + 2 comments

      How does this algorithm deal with repeated elements?

      • PU
        purbanski + 1 comment

        From problem description : "Consider an array of distinct integers "...

        • AD
          anshumaan_dash + 0 comments

          My bad. :p

      • noobCoder1997 + 0 comments

        there are no repeated elements ...all the elements are distinct.check the problem statement

    • SidSam + 0 comments
      [deleted]
    • IK
      gara314 + 0 comments

      Thank you for reverse. Min sum could be for ascent order as well as for decent order.

    • hemanth_kgp + 1 comment

      How to map in c without dictionaries??Direct addressing would take lot of storage which is dependant on values of the input sequence..?

      • AP
        AKSHAY97 + 0 comments

        You can't map in c. You need to use c++ language

    • ayushr2 + 1 comment

      could you pls explain why we reverse the list and run the same algorithm? i wrote a solution which is exactly same but I had not compared with the reversed list. So i was failing in some TCs. But i fail to see how sometimes reverse gives you the correct answer.

      • MM
        mark_anthony_ma1 + 1 comment

        Yes could someone please explain why just checking the reverse is exhaustive enough?

        • SD
          dshan1 + 0 comments

          Sorting in either ascending or descending order will give us a beautiful array, but based on the original array, swapping to two different orders will give us two different results, and we want the smaller one

    • kbhaskar580 + 1 comment

      ur algo really helped me a lot...thank u..keep helping..

      • PU
        purbanski + 0 comments

        This is really nice comment. Thank you :)

    • AV
      abhishekvanjani + 1 comment

      will this work if array has same entries, as key for a map MUST BE UNIQUE??

      • PU
        purbanski + 0 comments

        I wrote it 8 months ago :) anyway - definetly algo would need to be updated if entries are not distinc. However - from problem description : "Consider an array of distinct integers "...

    • VS
      vaibhavpseud + 0 comments

      I used this logic, everything works but tests #1,#2,#3,#6 fail. Is there something special for these tests which needs to be handled & which is not mentioned in the threads?

    • J
      joaonoch + 0 comments

      CPP14 Implementation:

      #include <iterator>
      #include <map>
      
      using namespace std;
      #define FOR(i,n) for(long (i)=0;(i)<(n);((i)++))
      
      int main() {
          map<long,long> iMap, iMap2;
          long iNum, index1, index2; cin >> iNum;
          index1=index2=0;
          long iArr[3][iNum];
          FOR(i,iNum){
              cin >> iArr[0][i];
              iMap[iArr[0][i]]=i;
          }
          iMap2=iMap;
          copy_n(iArr[0],iNum,iArr[1]);
          copy_n(iArr[0],iNum,iArr[2]);
          sort(iArr[1],iArr[1]+iNum);
          FOR(i,iNum){
              if(iArr[1][i]!=iArr[0][i]){
                  index1++;
                  iArr[0][iMap[iArr[1][i]]]=iArr[0][i];
                  iMap[iArr[0][i]]=iMap[iArr[1][i]];
              }
              if(iArr[1][iNum-1-i]!=iArr[2][i]){
                  index2++;
                  iArr[2][iMap2[iArr[1][iNum-1-i]]]=iArr[2][i];
                  iMap2[iArr[2][i]]=iMap2[iArr[1][iNum-1-i]];
              }
          }
          cout << min(index1,index2);
          return 0;
      }
      
    • ashley247 + 0 comments
      import java.io.*;
      import java.util.*;
      import java.text.*;
      import java.math.*;
      import java.util.regex.*;
      import java.util.Collections.*;
      public class Solution {
      
          public static void main(String[] args) {
              /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
              Scanner sc = new Scanner(System.in);
              int n,count=0,count1=0;
              n= sc.nextInt();
               int []b= new int[n]; 
             Integer []a= new Integer[n]; 
              int []c= new int[n];
            HashMap map = new  HashMap();
             HashMap map1= new HashMap();
              for(int i=0;i<n;i++){
                  int num=sc.nextInt();
                  map.put(num,i);
                  map1.put(num,i);
                  a[i]=num;
                  b[i]=num;
                  c[i]=num;
              }
              
             Arrays.sort(a);
             
                 for(int i=0;i<n;i++){
                     if(a[i]!=b[i]){
                         count++;
                       int temp= b[(int) map.get(a[i])];
                         int x=b[(int) map.get(a[i])];
                        b[(int) map.get(a[i])]=b[i];
                         b[i]=temp;
                        map.put(b[(int) map.get(a[i])],(int) map.get(b[i]));
                         
                     }
                 }
              Arrays.sort(a,Collections.reverseOrder());
              for(int i=0;i<n;i++){
                     if(a[i]!=c[i]){
                         count1++;
                       int temp= c[(int) map1.get(a[i])];
                         int x=c[(int) map1.get(a[i])];
                        c[(int) map1.get(a[i])]=c[i];
                         c[i]=temp;
                        map.put(c[(int) map1.get(a[i])],(int) map1.get(b[i]));
                         
                     }
                 }
              if(count1>count)
                 System.out.println(count);
              else
                   System.out.println(count1);
          }
      }
      

      Doesnt run for test case 2 3 and 9 Why???

    • IS
      ishansrivastava1 + 0 comments

      "Then you need to execute it on input list and reversed input list - the smaller return value - is the answer." CAN YOU PLEASE EXPLAIN WHAT IS THIS LINE? I DIDNT GET IT

    • devinludwig + 0 comments

      This approach in Ruby:

      n = gets.to_i
      a = gets.strip.split.map &:to_i
      def find_swaps(a)
          map = a.each_with_index.map{|x,i| [x,i]}.to_h
          swaps = 0; sort = a.sort
          for i in 0...a.size do
              if sort[i] != a[i]
                  swaps += 1
                  map[a[i]] = map[sort[i]]
                  a[map[sort[i]]], a[i] = a[i], sort[i] end end
          swaps end
      puts [find_swaps(Marshal.load(Marshal.dump(a))),find_swaps(a.reverse)].min
      
    • AM
      aishm_149 + 0 comments

      I tried to implement your algorithm but I am getting half test cases as wrong answer. Can you help?

      include

      using namespace std;

      int main() { int n; vectora; cin>>n; int u,temp1; maph; for(u=0;u>temp1; a.push_back(temp1); h[temp1]=u; } vectorb(a.begin(),a.end()); vectorc(a.begin(),a.end()); sort(b.begin(),b.end()); int count_a=0; int count_b=0; int i,j,sec; for(i=0;i()); for(i=0;i

    • SK
      skvit001 + 0 comments

      I came up with a similar but not exactly the same approach in which i just counted mismatches and thought to apply some function on mismatches that would directly give swaps:

      if mismatches%2:
          return mismatches//2 + 1
      else:
          return mismatches//2
      

      But it somehow fails test case 1, 2, 3, 6. In the end I decided to go with actually swapping and counting it

      Isn't there any such function that could direcly be applied on mismatch count to yield number of swaps?

  • annjohny10 + 2 comments

    Finally solved it! Spent some time trying to figure out the hidden details. Would appreciate if there had been another test case. Things i learnt - Java specifics (might be useful if you're stuck):

    1. You have to sort the array in both ascending and descending order as both will yield a minimum sum.
    2. Remember to use a LinkedHashMap (if you are using one) and not a HashMap to store the element key and index value (to preserve insertion order).
    3. A copy of an ArrayList is a shallow copy. You need to addAll(originalArray) to create another array with the same values as the originalArray.

    The algorithm is pretty simple: (just a brief run-through , note the details, figure out the implementation)

    • compare every element of original array with a copy of the sorted array (refer 3)
    • when there's a mismatch, swap elements into their respective positions
    • count the total number of swaps
    • repeat the above with the array reversed (refer 1)
    • use a hashmap as a cache/lookup to speed things up O(1) (refer 2).

    Example:

    7 3 0 4 1 6 5 2 - original array

    0 1 2 3 4 5 6 7 - sorted array

    0 3 7 4 1 6 5 2 - after first swap

    0 1 7 4 3 6 5 2 - after second swap

    0 1 2 4 3 6 5 7 - after third swap

    0 1 2 3 4 6 5 7 - after fourth swap

    0 1 2 3 4 5 6 7 - after fifth swap

    Did you notice the pattern? All the best!

    • belushkin + 0 comments

      Great, thank you for the help, I will check it later!

    • sayansingha + 0 comments

      hey, if the numbers in the unsorted array are not serial then what do we do? for example: original array: 72 3 0 4 1 6 5 2 thanks

  • nikhil_gupta3591 + 1 comment

    Problem could be intresting if you try to solve it for array having duplicate elements.

    • ayushr2 + 0 comments

      my solution handles duplicates elements its not really challenging.

      n = int(input())
      l = list(map(int, input().split()))
      
      sort = sorted(l)
      rev = list(reversed(l))
      
      d = {}
      for i in range(n):
          if sort[i] not in d:
              d[sort[i]] = i
      
      swaps = 0
      i = 0
      while i < n:
          if sort[i] == l[i]:
              i += 1
              continue
          swaps += 1
          l[d[l[i]]], l[i] = l[i], l[d[l[i]]]
          d[sort[i]] += 1
      
      d = {}
      for i in range(n):
          if sort[i] not in d:
              d[sort[i]] = i
      
      swaps_rev = 0
      i = 0
      while i < n:
          if sort[i] == rev[i]:
              i += 1
              continue
          swaps_rev += 1
          rev[d[rev[i]]], rev[i] = rev[i], rev[d[rev[i]]]
          d[sort[i]] += 1
      
      print(min(swaps, swaps_rev))
      
  • kimsj2435 + 0 comments

    Have to compare ascending/descending order because we have to get minimum swap count.

    They have different swap count so you have to print smaller one.

    I used cycle algorithm for counting it.

    you can reference below site.

    http://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

  • VG
    victorgf + 2 comments

    In this problem, my intuition was telling me to just count the different positions between the input array and the sorted input array and then divide this count between 2 rounding up. For example: input array: 1 5 3 4 sorted array: 1 3 4 5 count: 0 1 1 1 = 3 number of swaps = ceil(3/2) = 2

    In all the cases that I have tried I get the correct answer. I take into account normal and reverse order. However, test cases #1,#2,#3,#6 give me a wrong answer. Could someone tell me the problem in my reasoning or give me a counter example?

    • sergiu_nacu + 0 comments
      [deleted]
    • goodengineer + 0 comments

      Hey, counter example here:

      5
      3 4 2 1 5
      

      the expected output is 3, but with your logic:

      3 4 2 1 5
      1 2 3 4 5
      ---------
      1 1 1 1 0
      
      &&
      
      3 4 2 1 5
      5 4 3 2 1
      ---------
      1 0 1 1 1
      

      the output is ceil(4/2) = 2

      The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.

  • ML
    linddd + 1 comment

    I thought I could solve this problem by quicksorting the array and then counting the number of swaps.

    No other person did it this way and I was unable to get it to pass for more than the first test case. I guess I misunderstood the problem somehow.

    Why wouldn't my approach work?

    • NB
      nishant4317 + 1 comment

      I tried the same but i think its because quicksorting takes a lot of time to partition and then recounting them takes a lot of time

      • RichArt + 1 comment

        Well, I tried with merge sort. And merge sort takes like quicksort O(n log n) time. This is pretty fast. But anyway the timeout was not the problem. The problem is that it produces wrong answers. Has anyone an idea how this problem differs from the classic inversion count problem?

        • RichArt + 0 comments

          Ok, I think I got it: This problem is not about the number of inversions. It is about the minimum number of swaps.

  • darshan_makwana + 0 comments

    import java.io.; import java.util.;

    public class Solution {

     static int size;
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    
    
       Scanner input=new Scanner(System.in);
    
        size=input.nextInt();
    
        //used for ascending order
        Integer ar[]=new Integer[size];
    
        // this will be used for decending array
        Integer copy_ar[]=new Integer[size];
    
        //store sorted array
        Integer sort_ar[]=new Integer[size];
    
        // store the index of array
        HashMap <Integer,Integer> map=new HashMap<>();
        HashMap <Integer,Integer> desMap=new HashMap<>();
        int ascOrder,desOrder;
        for(int index=0;index<size;index++)
        {
    
           ar[index]=input.nextInt();
    
            map.put(ar[index],index);
        }
    
    
        desMap.putAll(map);
        copy_ar=ar.clone();
        sort_ar=ar.clone();
        Arrays.sort(sort_ar);
    
    
         ascOrder=countSwap(ar,map,sort_ar);
        Arrays.sort(sort_ar, Collections.reverseOrder());
    
        desOrder=countSwap(copy_ar,desMap,sort_ar);
    
        if(ascOrder<desOrder)
        {System.out.println(ascOrder);}
        else
        {
            System.out.println(desOrder);
        }
    }
    
    
    public static int countSwap(Integer ar[],HashMap<Integer,Integer> map,Integer sort_ar[])
    {
    
        int count=0;
        int swapIndex;
    
        for(int index=0;index<size;index++)
        {
    
    
            if(sort_ar[index]!=ar[index])
            {
                swapIndex=map.get(sort_ar[index]);
    
    
                map.put(sort_ar[index],index);
                map.put(ar[index],swapIndex);
                ar[swapIndex]=ar[index];
                ar[index]=sort_ar[index];
                count++;
            }
    
        }
     //   System.out.println(map);
    
        return count;
    
    }
    

    }

  • anshul_4ggarwal + 0 comments

    My C++ Solution, Passing all test Cases :D

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int lilysHomework(vector <int> arr, vector<int> asc, vector<int>des, int length, map <int, int> maps) 
        {
        int swaps = 0;
            map<int, int> :: iterator it;
            for(int i=0; i<length; i++)
                {
                    if(asc[i] != arr[i])
                    {
                        //find the index of the element from the map
                        it = maps.find(asc[i]);
                        int index = it->second;
                        swap(arr[i], arr[index]); //swap performed
                        
                        //updating the maps value
                        it = maps.find(arr[index]);
                        it->second = index;
                        swaps+=1;
                    }
            }
        return swaps;
        }
    
    
    int main() {
        int n;
        cin >> n;
        map <int, int> maps;
         
        vector<int> arr(n);
        vector<int> asc(n);
        vector<int> des(n);
        
        for(int arr_i = 0; arr_i < n; arr_i++){
           cin >> arr[arr_i];
           maps.insert(pair <int, int> (arr[arr_i], arr_i));
        }
        
        asc = arr;
        des = arr;
        
        sort(asc.begin(), asc.end());
        sort(des.begin(), des.end(), greater<int>());
        
        //Finding the swaps by comparing input data array withascending Sorted array
        int result = lilysHomework(arr, asc, des, n, maps);
    
        //Finding the swaps by comparing the input data array with Descending sorted array
        maps.clear(); //Reset the maps
        for(int i=0; i<n; i++)
            maps.insert(pair <int, int> (arr[i], i));
        int result2 = lilysHomework(arr, des, asc, n, maps);
        
        cout<<min(result, result2)<<endl;
        return 0;
    }
    
  • zhangyingzi3 + 1 comment

    Help! What's the problem with my code? I can't pass the test cases. int lilysHomework(vector arr) { // Complete this function long min=INT_MAX, cnt=0,idx=0; for(long i=0;i

    • zhangyingzi3 + 0 comments
      long min=INT_MAX, cnt=0,idx=0;
          for(long i=0;i<arr.size()-1;i++){
              min=arr[i];
              idx=i;
              for(long j=i+1;j<arr.size();j++){
                  if(arr[j]<min){
                      min=arr[j];
                      idx=j;
                  }
              }
              if(arr[i]!=min){
                  swap(arr[i],arr[idx]);
                  cnt++;
              }
          }
          return cnt;
      

      long min=INT_MAX, cnt=0,idx=0; for(long i=0;i

  • Varaug28 + 0 comments
    int n; 
        cin >> n;
        vector<pair<long long,int> > v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i].first;
            v[i].second = i;
        }
        sort(v.begin(),v.end(),comp);
        int count = 0; 
        for(int j = 0; j < n; j++){
            if(v[j].second!=j){
                int x;
                for(int i = j+1; i < n; i++){
                    if(v[i].second==j){
                        x = i; break;
                    }
                }  
                v[x].second = v[j].second;
                v[j].second = j;
                count++;
            }
        }
        cout << count;
    

    Why the above code is not passing all test cases? this code simple checks the index of element with the rank after sorting and if it don't matches with the rank just find the element with index of the rank and swap the index values of both