Minimum Swaps 2

Sort by

recency

|

2460 Discussions

|

  • + 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
    
  • + 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;
        }
    
  • + 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;
    }
    
  • + 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;
        }
    
  • + 0 comments

    O(n)

    int minimumSwaps(int n, const vector<int>& arr) {
        vector<vector<int>> cycles;
        vector<bool> visited(n+1);
        for (int i = 1; i <= n; ++i) {
            if (visited[arr[i]]) continue;
            cycles.push_back({arr[i]});
            int travel = arr[i];
            visited[travel] = true;
            while (arr[travel] != cycles.back()[0]) {
                cycles.back().push_back(arr[travel]);
                travel = arr[travel];
                visited[travel] = true;
            }
        }
        int moves = 0;
        for (vector<int> cycle : cycles) moves = moves + cycle.size() - 1;
        return moves;
    }
    
    int main()
    {
        int n, k;
        vector<int> arr = {-1};
        cin >> n;
        for (int i=1; i <= n; ++i) {
            cin >> k;
            arr.push_back(k);
        }
        cout << minimumSwaps(n, arr);
    }