Same for the problem statement: 1 <= arr[i] <= n

Lol

You don't need to alalyze and swap the last element. Run your loop from 0 to less arr.length-1. It passes all the tests.

Yeah, I kept getting a runtime error and then realized it wasn't on me.

So it's been 3 months since this was brought up and there's still no change in that one test case...

A lot of these are flawed

I face the same confusing issue

This test case should be removed :( It doesn't follow consecutive numbers rule...

Weird

just normalize the input while reading, for example we have the following input:

5

1 2 77 3 18

1st step: While reading we are finding the maximum number that fits our constraints < N.

2nd step: If it >= N, then add it to a map (key-value), where the key is that number you read and the value is the position of this element in the array

So here we are done with reading the array.

3rd step: Order this map by key ascending and replace all numbers in your array to the fictive ones (like foreach (var pair in sortedMap) { Array[pair.Value] = maximumNumber++})

So we will get a new one array:

1 2 5 3 4

And then everything will be alright

Hi, here is my code, and it works for test case 14 too.

I looped through each value in the array, then had a pointer that searched for an index in the array that holds the value meant to be at the current index.

    static void swap(int[] array,int left, int right){
        int temp = array[right];
        array[right] = array[left];
        array[left] = temp;
    }
		
static int minimumSwaps(int[] arr) {
        int rightPointer = arr.length -1;

        int count = 0;
        int minimumSwaps = 0;

        while(count < arr.length){
            int arrValue = count+1;

            if(arr[count] == arrValue){
                count++;
                continue;
            }

            while(arr[rightPointer] != arrValue){
                rightPointer --;
            }

            if(rightPointer != count){
                swap(arr, count, rightPointer);
                minimumSwaps++;
            }

            rightPointer = arr.length -1;
            count++;
        }
        return minimumSwaps;
    }

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n]

Because life is not a fair :) And we imitate here real world development process, right?)

Here is my c# code with O(2n) time complexity

Just use dictionary or hasmap to store indexes and update it as you proceed in the 2nd loop.

Dictionary indexDict = new Dictionary(); int countMinSwaps = 0;

    for(int index = 0; index < arr.Length; index ++){
        indexDict[arr[index]] = index;
    }

    for(int index = 0; index < arr.Length; index++){
        if(arr[index] == index + 1)
            continue;
        else{
            int swappingIndex = indexDict[index + 1];
            int temp = arr[index];
            arr[index] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            indexDict[index + 1] = index;
            indexDict[arr[swappingIndex]] = swappingIndex;
            countMinSwaps++;
        }
    }

    return countMinSwaps;

static int minimumSwaps(int[] a) { int n=a.length; int i,temp,swap=0; for(i=0;i

    a[temp]=a[i];
    a[i]=i+1;

    swap++; 
  }

}

return swap; }

Can you please explain the logic behind this?

I have also done this approach, but it is getting "Terminated due to timeout"

Here is my code int n = arr.length; int count = 0; for(int i=0; i

simple and elegant solution.

My code solves all test cases

https://www.hackerrank.com/challenges/minimum-swaps-2/forum/comments/467350?h_l=playlist&slugs%5B%5D=interview&slugs%5B%5D=interview-preparation-kit&slugs%5B%5D=arrays

It works, but technically you're not supposed to modify the loop variable within the body of a for loop because it's a bad programming practice. You should have used a while loop to avoid that.

Please modify your solution like the following to avoid index out of bound

int minimumSwaps(vector<int> arr) {
int i,c=0,n=arr.size();
for(i=0;i<n;i++)
{
    if(arr[i]==(i+1))
        continue;

   if(arr[i]-1>=0 && arr[i]-1<arr.Length)
    {
        swap(ref arr[i],ref arr[arr[i]-1]);
        c++;
        i--;
    }
}
return c;
    }

no bro the array elements are not in a order , the input can be 4 1 7 5 3

wrong process.

In question nowhere its mentioned that the array element will always consists 1,2,3..... . if the array starts with suppose 234 and the array size is 40 only your code will give runtime error.

this code havent solved the situation when arr[i] > n ,i think

Can you please explain i-- ?

Cool algorithm. A python translation for your code (and a fix for the current test case data bug):

def minimumSwaps(arr) :    
    swap=0
    i=0
    while i<len(arr):
        #Bug in input data which violates problem constraints
        if len(arr)==7 and i==6:
            break
        if arr[i]==(i+1):
            i+=1
            continue
        arr[arr[i]-1], arr[i] = arr[i], arr[arr[i]-1]
        swap+=1
    return swap

cool, I solved the same way in C#

This solution throws a segmentation fault on test 3 when copied directly into the C++ editor.

Thats incorrect

for n=7 and arr=1 3 5 2 4 6 8 your code gives answer 4 instead of 3

Great, but your solution seems need supplement. It didn't get through some test cases.

i am getting a timeout for the same kind of solution. please help!

Genius.

cute. This will always work because, the input set is consecutive unordered positive integers and swapping is based on positions. At nth iteration, the nth element will be put to it's correct position.

Makes us realize how important just reading a question is.

high applauds ,really supr logic

I tried solving it with one loop and that i-- is what I needed haha clever shit! Thanks!

I think continue is unnecessary here we don't have to check for the numbers that are already in their respective places . we can simply swap the numbers that are not in their right position

this is enough

 if(a[i]!=(i+1)){
        swap(a[i],a[a[i]-1]);
      count++;
       i--;
    }
		

Nice approach. I was skeptical that it will count the minimal swaps, so I went with mapping solution.

How can you be sure this will count the minimal swaps?

Is it a well-known algorithm?

The solution works, but it would be great if you could tell how did you come up with that logic

This is really cool. What sorting algorithm is this or did you just came up with it?

My solution is more verbose but it is similar to yours, gets all test cases right and is only requesting the sequence to be not containing any duplicates. Gaps in the sequence are okay and the sequence may also start at any non-negative value

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    #principle: trying to swap with maximum impact
    #iterations (reads) are cheap, swapping expensive
    #if two values can be swapped where both receive terminal position afterwards, perfect
    swaps = 0
    min = None
    for i in arr:
        if min is None or min > i:
            min = i
    #defined a min, which is at 0, let's make sure it's at i=0
    min_i = arr.index(min)
    if min_i is not 0:
        swap(arr, 0, min_i)
        swaps+=1
    
    #because the minimum is at 0 and they are all consecutive, it's basically an offset
    offset = arr[0]
    
    #initializing a dict copy that keeps track of the locations for quick find and swap
    index_dict = {v: i for i,v in enumerate(arr)}
    #starting at 1, 0 is already placed
    i = 0
    while i < len(arr)-1:
        i += 1
        if not proper_place(arr, i, offset):
            try:
                val = arr[i]
                #testing for perfect swap
                if arr[val - offset-1] == i:
                    swap(arr, i, val - offset)
                    swaps+=1
                #no perfect swap possible, find item that belongs here and swap this one away
                else:
                    j = index_dict[i+offset]
                    index_dict[arr[i]] = j
                    swap(arr, i, j)
                    
                    swaps+=1
            except:
                pass
    return swaps
                
            
        
def proper_place(arr, i, min):
    return arr[i] - min == i

def swap(arr, a, b):
    t = arr[a]
    arr[a] = arr[b]
    arr[b] = t

Thanks! I was having a hard time understanding why my programm was so slow, I did a little of search and I had find these pages:

• https://wiki.python.org/moin/TimeComplexity
• https://stackoverflow.com/questions/5913671/complexity-of-list-indexx-in-python

Hope it will help anyone to understand this better.

Thanks! Super helpful. It is really a trade off btwn space and time.

I have doubt about this 2 lines of code

index_dict[v] = to_swap_ix

index_dict[correct_value] = i

What is this 2 lines of code actually doing? what will happen if I dont include this 2 lines? Thank you in advance

Because of the relationship between the index and the correct_value, I don't think you even need the ref_arr. You can just replace:

correct_value = ref_arr[i]

with:

correct_value = i + 1

but I'm unsure if that's easier for readability or not.

Yeah, I'm stuck in there too. My solution for any numbers no consecutives run out of time, and the solution for consecutives fails on the testcases with the same example you showed.

Whats wrong, it seems they have added that testcase-14 not far ago. Anyway for that test case we need to tweak the solution and it pass it:

static int minimumSwaps(int[] arr) {
        int arrLen = arr.length;
        int count = 0;
        int [] sarr = arr.clone();
        Arrays.sort(sarr);
        
        for (int i = 0; i < arrLen; i++) {
            if (arr[i] != sarr[i]) {
                count++;
                for (int j = i + 1; j < arrLen; j++) {
                    if (arr[j] == sarr[i] ) {
                        int tmp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = tmp;
                        break;
                    }
                }
            }
        }
        return count;
    }

One may want to remap the values into, say, 0, 1, ..., n - 1 ordered in the same way. This is possible in O(n log n) time:

vector<int> GetMap(const vector<int>& arg){
    vector< pair<int, int> > valToIndex;
    for (int i = 0; i < arg.size(); ++i){
        valToIndex.emplace_back(make_pair(arg[i], i));
    }
    sort(valToIndex.begin(), valToIndex.end());
    vector<int> res(arg.size());
    for (int i = 0; i < arg.size(); ++i){
        res[valToIndex[i].second] = i;
    }
    return res;
}

As a side note, I really hope that there will be no new testcases with repeated entries. The problem with repeated entries is likely to be NP-hard for reasons similar to https://math.stackexchange.com/questions/2419271/decomposition-of-edges-of-eulerian-graph-into-maximum-number-of-cycles

Yep, it's a different problem if the numbers aren't actually consecutive. If they want to keep those abberrent test cases, they should remove the word consecutive from the problem and make most of the test cases simply be an array of integers with no duplicates, not integers that are nearly consecutive, with a single exception.

The spec also says that the first line of input is n, and that arr[i] <= n. But in that example, arr[6] == n + 1!

So that test case is clearly wrong, the correct test case should be:

7 
1 3 5 2 4 6 7

Hi friend, You don't need to check the last element, because in your while, you know that arr[i]>=i iterator < arr.Length-1

Really a simple solution !!

m using d same algorithm in python ...but doesnt pass 4 testcase ... Can anyone tell me why it is happening ?? my code is

def minimumSwaps(arr):
    swap=0
    for i in range (len(arr)):
        if(arr[i]!=(i+1)):
            t=i;
            while(arr[t]!=(i+1)):
                t+=1
            temp=arr[t]
            arr[t]=arr[i]
            arr[i]=temp
            swap+=1
    return swap

The swapping using temp is not really required. You know that the value at a[t] should be a[i] and that the value at a[i] should be i+1.

so all you need is : a[t] = a[i] and a[i] = i+1

@anandsingh9123 @shgpt14
This is O(n^2).
E.g. 4 2 3 1
In the while loop:
when i = 0
t will go from 0 to n-1, since a[n-1] = i+1 = 1


You are basically doing insertion sort. Time complexity is going to be O(n^2). There are better solutions with O(n) discuessed in other posts.

this solution will never work for the test cases. this will only return true, if all the elements are within the range of their indexes.

for example, for the following example: this will fail. 1. 2 3 4 5

throws IndexOutOfRangeException for Test Case 2 since it is not consecutive as said in problem description.

A very very nice solution. I was stuck on how to swap arr[i] and the actual i+1 value. That while loop is so smart!

Just for grins, copy-pasted this solution and it throws an exception....

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7 at Solution.minimumSwaps(Solution.java:17) at Solution.main(Solution.java:48)

I've used the same approach in javascript and got a timeout error. Any idea?

the for loop should run until a.length-1

Thank you, but you need to add a condition to avoid ArrayOutOfBoundException by replacing the line

if(i+1!=a[i])

with

if(i+1!=a[i] && i less than a.length-1)

for(int i=0;i

for(int i=0;i

use a.length-1

Why does the code give a segmentation fault when I use t+1 in while loop instead of i+1?

really a very simple solution. thank you

This looks simple but for performance wise this will not be appropriate solution.