[HackerRank] Minimum Swaps 2

Minimum Swaps 2

Problem

Link: https://www.hackerrank.com/challenges/minimum-swaps-2

Solution

// Complete the minimumSwaps function below.
int minimumSwaps(vector<int> arr) {

    pair<int,int> arrPos[arr.size()];
    for(size_t i = 0;i<arr.size();i++){
        arrPos[i].first = arr[i];
        arrPos[i].second = i;
    }

    sort(arrPos, arrPos + arr.size());

    int minSwap = 0;

    vector<bool> visit(arr.size(),false);

    for(size_t i = 0;i < arr.size();i++){

        if(visit[i] || arrPos[i].second == i){
            continue;
        }
        int cycle_size = 0;
        int j = i;
        while(!visit[j]){
            visit[j]=true;
            j = arrPos[j].second;
            cycle_size++;
        }

        if (cycle_size > 1){
            minSwap +=cycle_size - 1;
        }
    }

    return minSwap;

}

Leave a Reply

Your email address will not be published. Required fields are marked *