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. Minimum Swaps 2
  2. Discussions

Minimum Swaps 2

Sort by

recency

|

2461 Discussions

|

  • dubeykeshav98
     + 0 comments

    Python solution with all the base conditions : 

    def minimumSwaps(arr):
    
    arr_sorted = False
    current_pointer = 0
    swaps = 0
    
    while not arr_sorted :
        if (current_pointer == len(arr)) :
            arr_sorted = True
            break
        
        if (current_pointer+1 == arr[current_pointer]) :
            current_pointer += 1
        else :
            ind = arr[current_pointer] - 1
            arr[current_pointer], arr[ind] = arr[ind], arr[current_pointer]
            swaps += 1
        
    return swaps

  • despean
     + 1 comment
    def minimumSwaps(arr):
    i = 0
    swap = 0
    while i < len(arr):
        if arr[i] == i+1:
            i +=1
        else:
            index = arr[i] -1
            arr[i], arr[index] = arr[index], arr[i]
            swap += 1
    return swap

  • khandanish5
     + 0 comments

    Java 7: Uses Selection sort which guarantees minimum number of swaps.

        static int minimumSwaps(int[] arr) {
        int swaps = 0;
        for(int i = 0; i < arr.length; i++) {
            int minimum = Integer.MAX_VALUE;
            int minimumIndex = -1;
            for(int j = i; j < arr.length; j++) {
                if (arr[j] < minimum) { 
                    minimum = arr[j];
                    minimumIndex = j; 
                }
            }
            if (arr[i] != minimum) {
                int temp = arr[i];
                arr[i] = arr[minimumIndex];
                arr[minimumIndex] = temp;
                swaps += 1;
            }
        }
        return swaps;
    }

  • doomon
     + 0 comments

    I figure an index map can make it a whole a lot easier and straight forward:

    function minimumSwaps(arr) {
  const indexMap = {};
  arr.forEach((element, index) => {
    indexMap[element] = index;
  });

  let swap = 0;
  for (let i = 0; i < arr.length; i++) {
    //If the index doesn't match value, swap
    if (arr[i] !== i + 1) {
      const target = i + 1; //1
      const currTargetIndex = indexMap[target]; //index = 3

      //swap and keep track of the index map
      indexMap[target] = i;
      indexMap[arr[i]] = currTargetIndex;

      arr[currTargetIndex] = arr[i];
      arr[i] = target;

      swap += 1;
    }
  }
  return swap;
}

  • edoardo_cocconi
     + 0 comments

    My solution in java:

        static int minimumSwaps(int[] arr) {
        int minimumSwaps = 0;
        for (int i = 0; i < arr.length; i++) {
            int current = arr[i];
            while(current != i + 1){
                int temp = arr[current - 1];
                arr[current - 1] = current;
                arr[i] = temp;
                ++minimumSwaps;
                current = temp;
            }
        }
        return minimumSwaps;
    }