- Minimum Swaps 2
- Discussions

# Minimum Swaps 2

# Minimum Swaps 2

roby2358 + 17 comments "You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates."

1 3 5 2 4 6 8

huh?

karljholub + 0 comments Same for the problem statement: 1 <= arr[i] <= n

jeanno_cheung + 0 comments Lol

ahavriluk + 6 comments 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.

pentdown + 0 comments Priceless

juan_villgs + 0 comments This is wrong, you do need to test it.

chirayuasati19 + 0 comments I think it is absoultely right. Maybe, that's why there is that test case, who knows :P

Keeganjm + 0 comments You are correct, you only need to run your loop from 0 to less than arr.length - 1 because either: 1. The number which is supposed to go in the last index is in the first n - 1 indices, in which case we put it in its correct place at the last index or 2. The number which is supposed to go in the last index is already in the last index, in which case we do not need to look at it.

Therefore, it does not matter that we don't look at the last index.

sarangsbabu367 + 0 comments great buddy.....

sakshi_munya + 4 comments Can you plzz give the code,because there is only 3 cases passed from my code.

v1r33x + 1 comment [deleted]sumanconstantin + 1 comment Your comment is not formatted correctly.

Your solution is not optimal.

It passes not all tests (only 9).

Why do you flood the forum?

v1r33x + 1 comment Are you retarded?.i have already mentioned that its passes 9 tests . someone above requested for an answer (her answer only passed 3 tests) so i thought to provide her mine. she might get some insight and reach the correct answer.and i never said anything about my solution being the optimal one so keep you suggestion to yourself and if you dont like my solution that much , please from next time provide the correct answer to the person who requested for it.its would help all 3 of us. cheers!!.

sumanconstantin + 2 comments This is a community of hackers based on respect.

You won't get help if you disrespect someone.

If you can't stand critics and you react like a spoiled kid, then you won't learn anything.

A teacher is good only when he knows a correct answer.

If you know only half an answer, then you should not teach but should learn more.

If you don't have time to search for the best answer, but have time to brag about critics, then you'll learn nothing.

v1r33x + 1 comment Yeah . mistake from my side . I am sorry. :) . cheers!!

gary0 + 0 comments Actually for people who cannot figure out the correct answer, they can just go to the Editorial Tab and unlock the answer provided by the problem poster. They will not be awarded points if they try to solve the problem after this but that is fairly reasonable IMO.

cu_16bcs2416 + 0 comments i think only person bragging here is you.

v1r33x + 0 comments [deleted]v1r33x + 0 comments [deleted]eparas + 3 comments def minimumSwaps(arr): temp = [0] * (len(arr) + 1) for pos, val in enumerate(arr): temp[val] = pos pos += 1 swaps = 0 for i in range(len(arr)): if arr[i] != i+1: swaps += 1 t = arr[i] arr[i] = i+1 arr[temp[i+1]] = t temp[t] = temp[i+1] return swaps

168W1A0598 + 1 comment can you explain your code to me

eparas + 0 comments Well, I created a temporary array (temp) to store the position (pos) of elements (val) in the original array (since they are consecutive). Then I referred to the positions in order to bring the original array into order: I looked for 1, and wherever that 1 is, I placed the element at index 0 of arr and then updated its new position in temp as well; looked for 2, wherever that 2 is, I placed the element at index 1 of arr and then updated its new position in temp... If any element is at its right place, I skipped else increased the swaps.

vikas3549 + 0 comments [deleted]msravank6 + 1 comment i didnot understand ur code but it was some what similar to mycode..... can u please tell what's wrong in my code.....

and what is enumerate....???

def minimumSwaps(arr):

`count=0`

for i in range(len(arr)):

if(arr[i]!=i+1):

temp=arr[i]

arr[i]=arr[arr.index(i+1)]

arr[arr.index(i+1)]=temp

count+=1

return count

harikrishnnkv1 + 1 comment enumerate returns index as well as value,here he is creating an index list where values are indexes of first list and its indexes are old lists values. in his code yo can see a line "pos +=1" its actually not required.code will even work without this , In yor code you are using index function ,the problem with index function is if you having an array like this list1=[1,2,3,2,4] and you use a for loop to print indexs of list1 like this. < for i in list1: print(list1.index(i)) > the index list should be [0,1,2,1,4] here the function performing leniar search kind process.so it record only first occurance.that is the problem.

`here in his code he created a index list.and he take it as a reference,and along with each swap the index list is also update. in your code try to make a index list,it will help you`

c_m_s_gan + 2 comments I tried the following:

`def minimumSwaps(arr): counter = 0 for i in range(len(arr)): if (arr[i]) != i+1: l = arr.index(i+1) arr[i],arr[l] = i+1,arr[i] counter += 1 return counter`

Intuitively, this approach ought to be more concise and quicker than creating a separate list, but it actually takes significantly longer! (Tried timing it in another kernel; mine could take up to 3 to 4 times as long as eparas')

c_m_s_gan + 0 comments Update: Came up with the following codes that actually works quickly enough to elude the timeout error. I don't get why is it that using the ".index" appendment on the working list (the one whose entries are being swapped around) causes such a massive slowdown in performance!

`def minimumSwaps(arr): counter = 0 ph = [0]*(len(arr)) for index,val in enumerate(arr): ph[val-1] = index #while arr != sorted(arr): for i in range(len(arr)): #for j,number2 in enumerate(arr): #if j != i: #and (number1 - 1 - i) + (number2 - 1 - j) == m: if (arr[i]) != i+1: l = ph[i+1-1] #l = arr.index(i+1) arr[i],arr[l] = i+1,arr[i] #the 2 corresponding entries in ph have to be updated simultaneously! ph[i+1-1],ph[arr[l]-1] = i,l counter += 1 return counter`

mohith7548 + 1 comment [deleted]mohith7548 + 0 comments Hey that got me same Timeout error for some cases. I recoded it in C++. Now all cases done. Python do have some limits. Try reading @kunemohith/c-or-python3-for-competitive-programming-8ccbb7285498">this, this helped me a lot

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

jfmsouza + 0 comments [deleted]choubeyaakash77 + 1 comment So it's been 3 months since this was brought up and there's still no change in that one test case...

_mim_ + 1 comment I believe the sample is wrong, the explanation is correct, assume they are consecutive numbers

abhishek_r + 0 comments yes there is no 7 in the array and hence creates a confusion, but needs to be assumed.

shalomfriss + 0 comments A lot of these are flawed

AjaxianK + 0 comments I face the same confusing issue

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

harikrishnnkv1 + 0 comments then problem should be your code

mostafizur_cse + 0 comments Weird

Thorlake + 2 comments 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

leanhminh1292 + 4 comments Yeah, at first when I didnt notice that the array has to start from 1 and consecutive from there I was confuse too, since it mean we need a sorted array first to even check how many swap we will need in the end. Your 3rd step is basically a sort by itself, and if we have to sort anyway we can skip the whole normalize thing by doing this (in JS)

var origArray = arr.slice(0); // to keep a copy of the original array var sortedArray = arr.sort(); for(var i = 0; i < origArray.length; i++) { if (origArray[i] != sortedArray[i]) { for (var j = i+1; j < origArray.length; j++) { if(origArray[j] === origArray[i]) { swap(origArray[i],origArray[j] numberOfSwap++ break; } } } }

This way we dont have to worry about normalization at all since we know exactly where each value should be after the mandatory sort either way.

kwhiting + 1 comment this was super helpful! but you have some typos. fixes here:

var origArray = arr.slice(0); var sortedArray = arr.sort((a,b) => a - b); for(var i = 0; i < origArray.length; i++) { if (origArray[i] != sortedArray[i]) { for (var j = i+1; j < origArray.length; j++) { if(origArray[j] === sortedArray[i]) { swap(origArray[i],origArray[j]) numberOfSwap++ break; } } } }

lewisroryjames + 0 comments [deleted]

ryankawall01 + 0 comments [deleted]calatayud_zepeda + 6 comments Thanks for your input. I did something different and i think is faster (in JS).

`function minimumSwaps(arr) { // We know that the array will be sequential. So in order to calculate the finalPosition of each value we need to calculate the min value of the array. Next, see the finalPosition calculation. let minValue = Math.min(...arr); let finalPosition = 0; let buffer = 0; let numberSwaps = 0; let i = 0; // Process every value in the array. while (i < arr.length) { //Calculate the final finalPosition of each value. finalPosition = arr[i] - minValue; // Check wether the value is in its correct finalPosition. If not, throw (swap) it to its rigthfull position. if (finalPosition != i) { buffer = arr[i]; arr[i] = arr[finalPosition]; arr[finalPosition] = buffer; numberSwaps++; } else { // If the value is already in its final position, go to the next value. i++; } } return numberSwaps; }`

johnnyghi + 1 comment I dont ge the logic with posF = arr[i] - minValue. Can you elaborate?

calatayud_zepeda + 0 comments I edited my original post. I think is clearer now. What the algorithm is doing is throwing (swapping) the first element of the array back to its finalPosition.

You are always checking the first element of the array, unless that number is already in its finalPosition, in which case you go to the second element and so on.

So in order to do that, we must know which it's the finalPosition of each value, and that's what the formula that you mention does.

`finalPosition = (the value you are processing) - (the min value of the array)`

Since we know that the input array (arr) is always in sequential order, then we only need to know the min value (the value that it's final position will be index 0) and calculate the distance between the value you'r processing and the min value.

sumanconstantin + 1 comment 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?

AlexMiller + 0 comments I'm wondering this too. What is the proof this gives minimum number of swaps? it obviously passes all test cases, but how do you even come to the conclusion that this will give you minimum swaps? I'm just wondering in an interview, if the interviewer asked, how do you KNOW? What am I supposed to say?

saidihasan + 0 comments finalPosition = arr[i] - 1; will work too

prianka_mishra + 0 comments preety clean solution..

naseem_dotnet + 0 comments Very clear and precise. I was getting close to the correct answers but my logic had some issues. Thanks for your great input.

jameslingo + 0 comments [deleted]

boydevansu + 0 comments what does === mean?

gmadaan15 + 2 comments Even after normalising, 6 test cases are not cleared.

phatakmihir + 1 comment And Those test case numbers would be numbers 9,10,11,12,14?

gmadaan15 + 1 comment no, took care of those cases by normalizing it and than used minimum cycles approach to solve the problem.

It was not running intially because there were some print statements in between and it took me three days to figure out that this was the problem.

Advice: don't leave any debug print statemnts in between, even if the code is not atall depending on them(like in this case)

phatakmihir + 1 comment Thank you gmadaan15. I am a little confused as to what exactly you mean by minimum cycles approach? Do you mean minimum swaps or minimum iterations?

Also, do you think normaization is required here since all test cases are now fixed and arrays are contigious?Thank you!

gmadaan15 + 1 comment https://stackoverflow.com/questions/13549051/find-the-number-of-swaps-needed-to-sort-a-given-array

When those 6 test cases were not getting cleared, I moved to discussions to see if I can get any help. There, I got to know about one particular test case and hence added normalization

phatakmihir + 0 comments Makes sense. I am confused as to what you mean by normalization in this case? Does it mean checking the n integers for consecutive property and inserting elements if any missing elements are found? Thank you, apreciate your help

blackjar72 + 2 comments And yet a much simpler approach, using no map, no extra data structures at all, will pass. On paper its O=n^2, yet its quick enough to not time out and pass all tests. Just search with an inner loop from i+1 until you find it -- if it was before you'd have already swapped, and just be sure to break the inner loop when you find the swap.

kakondey701 + 0 comments Awsome

sumanconstantin + 0 comments Yes, but searching takes more time, as you said, up to n^2. That's why I chose to have one more array wich would hold the indeces of arr: arr2[arr[i]-1]=i;

which is similar to a map.

In this case the time is 2n.

Most of the hackerrank tests have a time-out error, if the algorithm is not the most efficient, that's why I choose efficiency as priority.

laryho18 + 0 comments [deleted]laryho18 + 6 comments 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; }

oleksii_filonov + 5 comments Come up with the similar solution, but moved both right and left pointers if numbers are already in place.

static int minimumSwaps(int[] arr) { int first = 0, last = arr.length - 1; int swaps = 0; while (first < last) { while (arr[first] == first + 1 && first < last) first++; if (first < last) { int temp = arr[arr[first] - 1]; arr[arr[first] - 1] = arr[first]; arr[first] = temp; swaps++; } } return swaps; }

Edited to remove the while loop for the last index as it doesn't make much sense here nor improving number of iterations

wekesa_clinton + 0 comments static int minimumSwaps(int[] arr) { int minimum = 0; int counter = 0; while (counter

2016_rajpreetsi1 + 0 comments BEST SOLUTION TO SOLVE IT IN PLACE RATHER THAN ADDITIONAL MEMORY, WAS THINKING SOMETHING SIMILAR BUT COULD NOT APPLY IT, THANKS FOR SOLUTION.

naimulhaquesagar + 0 comments pretty simple solution ........ helpful

diliniwis + 1 comment Please explain this section of the code. I really don't understand it.

`int temp = arr[arr[first] - 1];`

`arr[arr[first] - 1] = arr[first];`

`arr[first] = temp;`

Thank you so much.

naimulhaquesagar + 1 comment this section of code is swapping its value

diliniwis + 1 comment I know.

But why they use

`arr[arr[first-1]]`

instead of`arr[]-1`

???naimulhaquesagar + 0 comments sorry i can't explain it in comment box

it's little bit tricky

array is full with consecutive int value

so it is sure that in index 0 the value will be 1 as the array is consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates

so in arr[arr[first]-1] they are shifting the value to it's correct place

sumanconstantin + 0 comments 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?

shailavishah17 + 3 comments But what if number doesn't start from 1 and not in sequential order?

oleksii_filonov + 0 comments Hi Shailavi, This algorithm relies on the sequence starts from 1.

Adithya_18 + 0 comments Here we dont have that case, but you can still convert to the case here 1,2...n by finding the minimum number in the array and subtracting it with all elements. Then run your algorithm. But it needs to be sequential in that case too.

mayonesa + 0 comments - the problem is stated as necessarily including 1.
- if the input was in sequential order it could be just printed out as the sol'n

samuelonyeukwu2 + 1 comment Could you explain better I'm getting kinda lost

oleksii_filonov + 1 comment Hi Samuel, Iterate though the array from the beginning (presumably sequence starts from 1) and find the element in a wrong place. So if arr[i] != i+1 for example arr[1] = 3 this means the second element in the array with the value of

**3**should be in the third place arr[2] = 3. Put the element in his placeint temp = arr[arr[first] - 1]; arr[arr[first] - 1] = arr[first]; arr[first] = temp; swaps++;

Keep iterating finding and placing the element in the correct position until all of those are in place

`while (first < last)`

samuelonyeukwu2 + 0 comments I see it now, niceeeee

sandeepkrishnan1 + 1 comment I have implemented this logic using python. However for some testcases, it terminates due to timeout. Would appreciate little help here. Here's my code: def minimumSwaps(arr,sw = 0): count = 0; right = len(arr)-1 while(count

boruchsteinmetz + 0 comments [deleted]

paullb + 0 comments I wrote a smiliar solution (also in Python) but it didn't come anywhere close to running in time. My solution, like yours, ran in O(N^2) time which is too slow given that there are 100,000 elements.

skk_wilson + 0 comments This solution works with limited test cases. Try with one 0 in array

acebreacher + 0 comments You are given an unordered array consisting of consecutive integers âˆˆ [1, 2, 3, ..., n]

hellomici + 0 comments [deleted]drKraken + 0 comments Because life is not a fair :) And we imitate here real world development process, right?)

FaxMachin3 + 1 comment **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;`

sumanconstantin + 1 comment Since you go from i=0 to n-1, you don't need to set values to previous 'i', so deleting these two lines will make sense:

arr[index] = arr[swappingIndex];

and

indexDict[index + 1] = index;

Also, you don't need to check the last value, so it should iterate to: index < arr.Length - 1;

FaxMachin3 + 0 comments Thanks,

But I did that just to see if I'm going in the correct flow or not. I knew I can remove it.

pkumarandroid + 32 comments My solution

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

sheetansh + 1 comment [deleted]sheetansh + 1 comment [deleted]aditi_15 + 4 comments Bonjour! The logic is great but what if the numbers are not consecutive? because for the series 1 2 3 4 5 6 8 , 8 seems odd for the code and results in an exception. Can you please explain. Thanks:)

etcheve + 3 comments Bonjour, for me it is an error on the test not on the code if you read the description, numbers have to be consecutive Constraints: 1<=arr[i]<=n in that case n=7 so 8 it a non case

aditi_15 + 1 comment Je suis d'accord. merci beaucoup:)

MrV_JeeHan + 1 comment Essayez de lire les contraintes sÃ©rieusement

stabgan + 0 comments [deleted]

matthew_d_davis + 2 comments Has anyone confirmed that the 3rd sample case should be [1, 2, ..., 6, 7] and not [..., 6, 8]?

EDIT: confirmed that the problem statement is incorrect. The only constraint appears to be no duplicates.

alex_mukhopad + 1 comment It seems the only test case that fails is this one. When I tried to sumbmit solution it gave me maximum points with 1 failed test case.

trapeznikov_alex + 2 comments Because you do not need to analyze and swap the last element.

ahavriluk + 0 comments Bingo!

hiptobecubic + 0 comments That's a hack that happens to work because it's the last element that's wrong. The test case violates the constraints. It's an irrelevant test case that shouldn't be there. End of story.

mhd001 + 0 comments Comment from the future: the 3rd sample is now

7

1 3 5 2 4 6 7

pypmannetjies + 0 comments Agreed, the test case seems to break the constraints

atul_ + 1 comment you can just replace the (i+1) in if condition with sorted_arr[i].

vector sorted_arr(arr.begin(),arr.end()); sort(sorted_arr.begin(),sorted_arr.end());

map the index of all elements

mapping[ sorted_arr[i] ] = i;

and swap part will be replaced by

swap(arr[i], arr[ mapping[ arr[i] ] ]);

i think it should work for general elements in array

swojit + 0 comments That's how I did it before I realized that the example in which 7 is missing is wrong.

hanieh61_h + 0 comments I also encountered this problem when testing the code, but then pushed the submit bottun. The submission was successful ;)

sarthakkaryo + 0 comments **if the numbers are not consecutive this code right below will work**static int minimumSwaps(int[] a) { int swap=0,ctr=0,small=Integer.MAX_VALUE; while(ctr!=(a.length-1)){ for(int i=ctr;ia[i]){ small=a[i]; } } for(int i=ctr+1;i

Mayfair + 1 comment Can you please explain the logic behind this?

rr47061 + 3 comments The logic is very simple. Only available elements in the array are from "1 to n " .

step 1 : check if each array index is filled is current value . ( So, arr[i] ==i+1, since, index start from 0 , so need for increment of 1 as value is from 1 to n ).

step 2 : for the element not at its actual position. we simply replace the ith element with value at the (i-1)th position , as index is from 0 . and increase the count . And again decreasing the i of loop to check if again the value at ith position is (i+1) or not .

`finally , you will get your desired value. thanks.`

lic_nancy_torres + 5 comments I also though on that logic, but there is a test case where the numbers are not 1 to n

1 3 5 2 4 8 6

So in there is missing the 7, so when you try to move 8 from its position 5 to its position 7 crash, because the array do not have position 7.

Am I doing someting wrong on the logic?

kevald + 2 comments no , i think input sequence is wrong hence error ocured

lic_nancy_torres + 2 comments No, the example on the description in fact shows a case where the numbers are

**no consecutives**https://www.hackerrank.com/challenges/minimum-swaps-2/forum/comments/466653

kevald + 0 comments [deleted]kdjackson51 + 2 comments for (int i = 0; i < arr.length - 1; i++) { if (i < arr[i] - 1) { swap(arr, i, Math.min(arr.length - 1, arr[i] - 1)); minSwaps++; i--; } }

BoogieMcCracken + 1 comment This loops infinitely if 1 is not in the input array.

kdjackson51 + 0 comments true

Sufiyan + 1 comment Could you please explain the logic? How do you arrive to use Math.min() part? This is really fast. The one I have written is failing for Testcase 13.

`static int minimumSwaps1(int[] arr) { int currentMin = 1; int currentInd = 0; int minSwapsCount = 0; while (currentMin != arr.length) { for (int i = currentInd; i<arr.length; i++) { if (arr[i] == currentMin) { if (i == currentInd) { //It is already sorted.. currentInd++; currentMin++; break; } swap(arr, i, currentInd); minSwapsCount++; currentInd++; currentMin++; } } } return minSwapsCount; }`

trapeznikov_alex + 1 comment Don't break my eyes

static int minimumSwaps1(int[] arr) { int currentMin = 1; int currentInd = 0; int minSwapsCount = 0; while (currentMin != arr.length) { for (int i = currentInd; i < arr.length; i++) { if (arr[i] == currentMin) { if (i == currentInd) { //It is already sorted.. currentInd++; currentMin++; break; } swap(arr, i, currentInd); minSwapsCount++; currentInd++; currentMin++; } } } return minSwapsCount; }

Sufiyan + 0 comments Thanks @trapeznikov_alex May I know how to write the code in this style in comment editor? What is the key code have you used? Thanks.

tdprime + 0 comments Agreed. The first sentence of the problem says,

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

8 > 7, therefore illegal input.

I was able to work around their buggy test cases by doing,

j = min((int)arr.size(), arr[j]) - 1;

gyansingh1997 + 0 comments while taking input just replace any number greater than n with "n" fr(n){ cin >> temp; arr[i] = temp > n ? n : temp; }

Vestride + 0 comments I "fixed" my version by not iterating over the last item in the array.

etcheve + 0 comments Constraints: 1<=arr[i]<=n

that case is wrong, it doesn t respect the constraints

qasselephant + 0 comments instead of doing i+1 make your given array in sorted array and store into another array and place it at the place of i+1

Pythonologist + 0 comments Does that even make sense? In the 2nd step why would you replace the ith element with (i-1)th element when you have already checked that element for its correct position and passed it to be in its correct position by moving to the next.You are actually messing up the correctly placed elements too...

yanglp904921 + 0 comments But why the number of swap is minimal using this algorithm?

rishabh0_9 + 2 comments 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

rr47061 + 2 comments maybe , you are swapping the value in wrong way .

use this pattern : int temp= arr[arr[i]-1]; arr[arr[i]-1] =arr[i]; arr[i]= temp;

sasuke29 + 1 comment `int min,i,count=0; for(i=0;i< arr.size()-1;i++) { min = i; for(int j=i+1;j< arr.size();i++) { if(arr[j] < arr[min]) j = min; } swap(arr[i],arr[min]); count++; } return count; }`

I am getting run time error . Can you please explain what I am doing wrong.

15481A0598 + 0 comments In the j loop you need to increment 'j' not 'i'

if(arr[j] < arr[i]) { min=j; }

above 2 are errors..

ashubalike + 1 comment This worked to me. could you please explain how does this make a difference than using like int temp = arr[i]; arr[i] = arr[arr[i]-1]; arr[arr[i]-1] = temp;

shank_007 + 0 comments If you write : int temp = arr[i]; arr[i] = arr[arr[i]-1] ; arr[temp -1] = temp; You would get the desired output. The error creeps in because you have already changed arr[i] before calling the statement, arr[arr[i]-1] = temp.

Ashwini_1_n + 0 comments [deleted]

alidanish + 0 comments simple and elegant solution.

grsoratoor + 1 comment StrgAltEntf + 2 comments But it returns a "wrong" output of "2" for the non consecutive test case:

4

5 10 2 1

The resulting array would be 1 2 10 5 which needs another swap to be sorted, so the right result would be "3".

I think there is no algorithm that solves non consecutive test cases like the above one and all the other test cases.

Skipping the 8 in Test Case 2:

7

1 3 5 2 4 6 8

only works because 8 is on the correct position already.

dgaban + 0 comments check the Editorial section... the right solution (which works with non consecutive test cases) is right there.

sinhaanuj1996 + 0 comments //to handle non consecutive numbers

`map<int, int> M; for(int i = 0; i < arr.size(); i++) M[arr[i]] = i; map<int, int>::iterator it; int j = 0, swipe = 0; for(it = M.begin(); it != M.end(); ++it){ if(arr[j] != (*it).first){ int k = (*it).second; swap(M[arr[j]], M[(*it).first]); swap(arr[j], arr[k]); swipe++; } j++; } return swipe;`

mkmarathe1 + 0 comments [deleted]danman1979 + 0 comments 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.

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

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

pandi_asit91 + 0 comments wrong process.

pandi_asit91 + 1 comment 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.

fadetoblack72 + 0 comments The second constraint is 1 < arr[i] < n.

In order for a consecutive array of length n to start at a value greater than one, a value would have to exceed n.

Basically the constraints and test cases are not aligned.

daiict_201501188 + 0 comments [deleted]tuandinhminh1234 + 0 comments this code havent solved the situation when arr[i] > n ,i think

heisenberg_ab + 0 comments [deleted]Jrayasam + 0 comments Can you please explain i-- ?

CompSocialSci + 7 comments 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

a_moheimani + 1 comment could you please explain the test case data bug? I have very similar code (without the

`if len(arr)==7 and i==6: break`

statement) that passes 10/15 test cases.CompSocialSci + 1 comment The problem statement says all the numbers are drawn from a list of consecutive integers. That is violated in the one test case where there is no 7 in the list but there is an 8. I saw some somewhat obfuscated workarounds so I posted my much more obvious one.

hai_hit + 0 comments how do we know the result is the minimum swaps ? can you explain which code make it minimum?

steve_stoytchev + 0 comments [deleted]gregpoulos196111 + 0 comments could you please explain me what this line does? " arr[arr[i]-1], arr[i] = arr[i], arr[arr[i]-1] "

seems weird...

EDIT: hmm, think i found it it's like a,b = b ,a that simply exchanges position in a and b

taparia_nikhil + 0 comments can you please explain your code? thank you

ankitarane24 + 0 comments [deleted]rmgstorm + 1 comment Hi CompSocialSci, My code is below and quite similar to yours. But, I got "terminated due to timedout" error in some of the test case.

Can you please shed the light on why it is slower? Much appreciated.

def minimumSwaps(arr): swapcount = 0 idx = 0 for i in range(len(arr)-1): if arr[i] != i+1: idx = arr.index(i+1) arr[i], arr[idx] = arr[idx], arr[i] swapcount += 1 return swapcount

Tej_Pratap_Singh + 0 comments looks like the bug has been resolved now.

nyckevinwong + 0 comments cool, I solved the same way in C#

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

amanharitsh + 1 comment Thats incorrect

liu_ruizhi + 0 comments why do you think that

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

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

manshitomarleo + 1 comment i am getting a timeout for the same kind of solution. please help!

trapeznikov_alex + 2 comments Where is your code?

Ashwini_1_n + 0 comments [deleted]Ashwini_1_n + 3 comments I used selection sort. getting terminated due to timeout for testcases 8 to 13.

int minimumSwaps(int arr_count, int* arr) { int count = 0,i,j,position,swap;

`for (i = 0;i<(arr_count - 1);i++)`

{ position = i;

`for (j=i + 1;j<arr_count;j++) { if (arr[position]>arr[j]) position = j; } if (position != i) { swap = arr[i]; arr[i] = arr[position]; arr[position] = swap; count++; }`

} return count; }

praveenbishtmar1 + 1 comment Same problem, how did you fix it ?

stabgan + 0 comments [deleted]

trapeznikov_alex + 0 comments Two for_loops is not a good idea. Try another logic.

abhijeetmonu15 + 0 comments can anyone explain why swapping of number is done?

OB3LISK + 0 comments Genius.

lindathadeus + 0 comments 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.

thebinarymutant + 0 comments Makes us realize how important just reading a question is.

pankajbelwal2012 + 0 comments high applauds ,really supr logic

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

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

sumanconstantin + 1 comment [deleted]sumanconstantin + 0 comments [deleted]

sumanconstantin + 0 comments 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?

chandruselv + 0 comments [deleted]jayjagtap_01 + 0 comments The solution works, but it would be great if you could tell how did you come up with that logic

mwwhite + 6 comments Here's a python3 solution that does not assume consecutive values but does assume that values aren't repeated. None of the test cases time out because it looks up indexes to swap using a hash table instead of the list.index method.

def minimumSwaps(arr): ref_arr = sorted(arr) index_dict = {v: i for i,v in enumerate(arr)} swaps = 0 for i,v in enumerate(arr): correct_value = ref_arr[i] if v != correct_value: to_swap_ix = index_dict[correct_value] arr[to_swap_ix],arr[i] = arr[i], arr[to_swap_ix] index_dict[v] = to_swap_ix index_dict[correct_value] = i swaps += 1 return swaps

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

mwwhite + 1 comment It's not really a sorting algorithm since it's just comparing the values against a pre-sorted array to see if a swap is necessary.

amylinari + 0 comments Basically, you're scanning the original list, and at each step, checking if there's a lower value among the remaining elements. If there is, swap the current position with that element. Doing so turns out to be optimal, probably because you only have to traverse the list once (to the left ends up sorted), and you get at least one element, and sometimes two, in the correct place with each swap.

That part essentially is the same for all solutions.

As originally described, every number has a correct position which can simply be calculated, and thus, the array can be essentially inverted to get a lookup table of value positions. From there, swap targets can be taken by looking up the expected value expected in the current position. So if you're at index 0, if you don't contain 1, you look for the location of 1 in the LUT, etc. Basically the main loop integer is doing double duty as the position and expected value (adjust by 1). That solution can run in linear time, a.k.a. O(n).

However, a test case was introduced which puts a gap in the numbers. The simplest solution is scanning the remainder as you go instead of using a lookup table, but it runs in O(n^2) time overall, and so it fails because of the large N test case. Thankfully we can spare a bit more memory (around four times N), so it's possible to build both a sorted list of numbers O(n log n) at the outset, and also maintain a hashtable O(n) of their current positions as they're swapped around, then run the swapping, which runs in O(n) time, for an overall time complexity of O(n log n).

gabriell_vasile + 0 comments Python sorted() function uses TimSort

pascalwhoop + 0 comments 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

asdrubal + 0 comments 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.

rebeccachow99 + 0 comments Thanks! Super helpful. It is really a trade off btwn space and time.

prashantpandey01 + 0 comments 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

ricardoserradas + 6 comments Saw something. The statement says that the array consist of

**consecutive**integers, but the first input sample says:7 1 3 5 2 4 6 8

Whoa, was driving me nuts 'till I saw it :-)

By the way, the Test Case 14 is the same. Well, it's the only one, all the other passed with this solution:

var unsortedIndexes = new List<int>(); var swapSum = 0; for(int iterator = 0; iterator < arr.Length; iterator++){ while(arr[iterator] != iterator + 1){ var swapKey = arr[iterator] - 1; var temp = arr[iterator]; arr[iterator] = arr[swapKey]; arr[swapKey] = temp; swapSum++; } } return swapSum;

lic_nancy_torres + 0 comments 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.rusyasoft + 6 comments 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; }

sneha391998 + 1 comment this logic is timing out for me.

alokmalakar2007 + 0 comments I second that.

eduasinco + 0 comments [deleted]wilkon + 0 comments Great logic! Made me rethink my strategy :) Thank You!

tijpra + 0 comments what if the break statement is added just outside the if statement ....It is showing error

princess_peach + 0 comments I want to know too. I have the same in python

magazinov_al + 0 comments 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

kvinklly + 0 comments 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

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.*consecutive*DouglasL + 0 comments 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`

idan_nik + 0 comments 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

anandsingh9123 + 17 comments a simple sol

static int minimumSwaps(int[] a) { int swap=0; for(int i=0;i<a.length;i++){ if(i+1!=a[i]){ int t=i; while(a[t]!=i+1){ t++; } int temp=a[t]; a[t]=a[i]; a[i]=temp; swap++; } } return swap; }

PavneetSingh + 1 comment Really a simple solution !!

armanalicid + 0 comments thank you very much, it's really a simple solution

shgpt14 + 4 comments 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

PavneetSingh + 1 comment By any chance you know what is the test case input.

mostafa_yahya_s1 + 0 comments because it takes more time to process than it is supposed to you have to decrease the run time

abhishekvelankar + 1 comment [deleted]stabgan + 1 comment [deleted]Mingling94 + 1 comment wow what an asshole . he's wrong on this point, doesn't mean you should insult his

abhishekvelankar + 0 comments thanks! but dont waste your time on such rookies!

sahilrider + 0 comments [deleted]palashjain14 + 0 comments The solution has complexity of O(n square), may be because of that.

karan_b755 + 0 comments 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

GauravEic + 0 comments @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

desaivaibhav94 + 0 comments 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.

hassan03 + 0 comments 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

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

dgaban + 0 comments [deleted]yd2386 + 0 comments 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!

claine + 0 comments 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)

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

Mingling94 + 0 comments Javascript will timeout for solutions 8 through 13. Hackerrank's fault :(

nishantketu903 + 0 comments the for loop should run until a.length-1

nbakr + 0 comments 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)

rie_miyazaki98 + 0 comments [deleted]kushalnagrani + 0 comments for(int i=0;i

shunmugapriyapa1 + 0 comments for(int i=0;i

use a.length-1

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

AbuZahedJony + 0 comments Sample Input 2 not following the input constraint 1<=arr[i]<=n

7 1 3 5 2 4 6 8

igor_v_fil + 2 comments A bit cleaner version of Java code that passes all test cases. Swaps in place for sake of simplicity

static int minimumSwaps(int[] arr) { int swaps = 0; for(int current=0; current<arr.length; ) { if(!inPlace(arr, current)) { ++swaps; swapInPlace(arr, current); } else { ++current; } } return swaps; } private static void swapInPlace(int[] arr, int index) { int newIndex = arr[index] - 1; int tmp = arr[newIndex]; arr[newIndex] = arr[index]; arr[index] = tmp; } private static boolean inPlace(int[] arr, int index) { return arr[index] == index + 1; }

darrylcdmello + 1 comment Could you please elaborate on the swapInPlace method.

Update: Never mind, I think I understood. Also since I feel theres no need to call the methods and the swap can be done within the for loop I have updated it to a version with everything done within the for loop.

`static int minimumSwaps(int[] arr) { int temp = 0, swaps = 0; for (int i = 0; i < arr.length;) { if (arr[i] != i + 1){ // System.out.println("Swapping --"+arr[arr[i] - 1] +" AND -- "+arr[i]); temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; ++swaps; } else ++i; // System.out.println("value at position -- "+ i +" is set to -- "+ arr[i]); } return swaps; }`

igor_v_fil + 0 comments I decided to split it following Single Responsibility Principle

luisdaza90 + 0 comments Excellent solution

lynsrz + 0 comments The question says consecutive integers from 1...n but we have test case as

`7`

`1 3 5 2 4 6 8`

mcam88 + 3 comments Gotta say, I'm very disappointed when the time constraints are such that the fastest way to solve something in Javascript continually gets a timeout. If HackerRank presents a problem then they should disable a language if they're going to put unrealistic time constraints on it.

Heres a solution I tried that worked other than timeout:

var rotArr = Object.values(Object.assign({}, arr)); var minVal; var maxVal = Math.max(...rotArr); var minValInd; var currentVal; var swapCount = 0; for(var i = 0; i < rotArr.length; i++){ // get minimum values minVal = Math.min(...arr); if(minVal === rotArr[i]){ arr.shift() continue; } minValInd = rotArr.indexOf(minVal); currentVal = rotArr[i]; rotArr[i] = rotArr[minValInd]; rotArr[minValInd] = currentVal; arr = Object.values(Object.assign({}, rotArr.slice(i))); arr.shift(); minVal = Math.min(...arr); swapCount = swapCount +1; } return swapCount;

Mingling94 + 1 comment Ditto on this, I was confused why my solution was timing out for test cases 8 through 13 until I saw this.

adamxtokyo + 3 comments The issue is not the language itself, but the boilerplate code they use to process test cases (JavaScript run in Node.js is actually generally speaking fast af). For some reason they use parseInt() instead of the Number constructor to parse integers, which slows it down A LOT.

This causes an issue when coders know JavaScript but aren't very familiar with Node.js, as they don't feel confident enough to change the surrounding code. I've been where you are though, and so I want to give you the help I never got.

Below is a full solution in JavaScript, including the test case parsing code. Hopefully, you can look at the code and learn from it:

'use strict' process.stdin.resume() process.stdin.setEncoding('ascii') let input_stdin = '' process.stdin.on('data', data => input_stdin += data) process.stdin.on('end', () => { let input = input_stdin.split('\n') let n = Number(input[0]) let arr = input[1].split(' ').map(x => Number(x)) process.stdout.write(minimumSwaps(n, arr) + '\n') }) // --- SOLUTION BELOW --- // function minimumSwaps (n, arr) { let swaps = 0 for (let i = 0, l = Math.max(...arr); i < l; i++) { while (arr[i] !== i + 1) { arr[i] = [arr[arr[i]-1], arr[arr[i]-1] = arr[i]][0] if (!arr[i]) break swaps++ } } return swaps }

AnonymousSB + 2 comments I'm fairly well versed in JavaScript, but I've never seen such in place swapping of elements. Is there a technical term for what you're doing here, or is this just crazy shorthand?

arr[i] = [arr[arr[i]-1], arr[arr[i]-1] = arr[i]][0]

wilpat456 + 1 comment Hi, have you been able to undersand what was going on with that line of code? Been trying to wrap my head arond it but It's got me bummed

gattaccio + 1 comment Yes, the performance killer is the indexOf on the array and the update of the array when you do the swap so you have to try avoiding that this is my recursive fn solution in Scala and goes really fast

def minimumSwaps(arr: Array[Int]): Int = {

`@tailrec def rec(lt: List[Int], sorting: Vector[Int], swap: Int, smallest: Int, track: Map[Int, Int]): Int = { lt match { case h :: t if h < smallest => val replaced: Int = track(h) rec(replaced :: t, sorting, swap, smallest, track - h) case h :: t if h != smallest => val newTrack = track + (smallest -> h) rec(t, sorting :+ smallest, swap + 1, smallest + 1, newTrack) case h :: t if h == smallest => rec(t, sorting :+ smallest, swap, smallest + 1, track) case _ => swap } } rec(arr.toList, Vector(), 0, 1, Map())`

}

IAmAbhiraj + 0 comments Can you explain what you're doing here? It's really hard to figure out recursion.

wilpat456 + 1 comment I think i've figured it out. He's basically doing a swap of

arr[i] and arr[arr[i] - 1]

You can achieve the same using the longer way:

var temp = arr[i];

arr[i] = arr[arr[i]-1]

arr[temp - 1] = temp

If you know python, you can implement this same code and use a more natural shorthand that python provides

a, b = b, a

AnonymousSB + 1 comment Thanks for the breakdown, makes sense now. I can say that I do not like it. Unreadable code has no place in real world programming.

wilpat456 + 0 comments Exactly. Even if you want to showcase your skills, i think showing the long method would make people actually appreciate the awesomeness of your shorthand method way better.

babylee2002 + 0 comments [deleted]babylee2002 + 0 comments With your help(Node.js), my code is finally passing..! (javascript)

//since the input is an array consisting of consecutive integers //use i to compare it's index function minimumSwaps(n,arr) { let swaps = 0 for (let i = 0; i < arr.length; i++) { if (arr[i] !== i + 1) { let temp = arr[i] let idx = arr.indexOf(i + 1) arr[i] = arr[idx] arr[idx] = temp swaps++ } } return swaps }

gattaccio + 0 comments Had same problem to start with and I was disappointed as well but if you really think about it the fun of this exercise is to fix the performance issue and has nothing to do with language - PS I read someone replying to your comment showing off with Node.js (LOL it's all I have to say)

Anyway have a second look at your code and try avoiding operations like updating the array and indexOf. These computations are the real performance killer. BTW my solution is in Scala if you want to have a look at it let me know

brian_aronowitz + 0 comments This may help, but creating a hashmap, mapping values to indices may help. My bottleneck was in using the default "indexOf" method, but creating a hashmap to do these checks helped speed immensely.

antoine11 + 1 comment Here is my solution using Javascript.

If you want to avoid timeout error and have a fast compute you'll need to create a map of each index based on value of the given array.

You also need to create an array sorted to know what value you should have next when you iterate and if it's not the one attended you can swap it. During the swap you need to update the map with the new index and voilÃ .

function minimumSwaps(arr) { let swaps = 0; let l = arr.length; // Copy array const arr2 = [...arr]; // Sorting the new array // It will be used to know what's the next value in the array // And swap if needed arr2.sort((a, b) => { if (a > b) return 1; else if (a < b) return -1; return 0; }); // Create an object with values of our array as keys // and position in array as values const map = arr.reduce((acc, cur, i) => { acc[cur] = i; return acc; }, {}); // Now we loop through the array for (let i = 0; i < l; i += 1) { const v1 = arr[i]; const v2 = arr2[i]; if (v2 != v1) { swaps += 1; // Use the map to avoid to compute each time the position const index = map[v2]; // swap value arr[index] = v1; arr[i] = v2; // Update map map[v1] = index; }; } return swaps; }

bryank + 1 comment Here's a shorter version, same logic but using a Map.

function minimumSwaps(arr) { const arr2 = arr.slice().sort((a, b) => a - b); const indexes = new Map(); arr.forEach((v, i) => indexes.set(v, i)); let swaps = 0; arr.forEach((v, i) => { if (v !== arr2[i]) { swaps++; arr[indexes.get(arr2[i])] = v; arr[i] = arr2[i]; indexes.set(v, indexes.get(arr2[i])); } }); return swaps; }

g_siddharth_in + 2 comments Don think we need two arrays..Here is a solution static int minimumSwaps(int[] arr) {

`boolean swapsNeeded=true; int swapLocation,temp,nSwaps = 0; while(swapsNeeded) { swapsNeeded = false; for(int i=0; i<arr.length;i++) { if(arr[i]!=(i+1)) { swapLocation = arr[i]-1; swapsNeeded=true; temp = arr[i]; arr[i] = arr[swapLocation]; arr[swapLocation] =temp; nSwaps++; } } } return nSwaps; }`

susahin80 + 0 comments `Hi, I converted this to javascript and it passes tests, but I couldnt understand where is the logic for minimum swaps?`

mojeskamlapure + 0 comments will this work for {2,3,4,1,7} it breaks as soon as the value of an element in array exceeds the length of the array

Sort 825 Discussions, By:

Please Login in order to post a comment