Minimum Swaps to sort intuition + code C++ with explanation

Given an array of n distinct elements. Find the minimum number of swaps required to sort the array in strictly increasing order.
Example 1:
Input:
nums = {2, 8, 5, 4}
Output:
1
Explaination:
swap 8 with 4.
Example 2:
Input:
nums = {10, 19, 6, 3, 5}
Output:
2
Explaination:
swap 10 with 3 and swap 19 with 5.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minSwaps() which takes the nums as input parameter and returns an integer denoting the minimum number of swaps required to sort the array. If the array is already sorted, return 0.
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(n)

[@arijitdey8419]

Very nicely explained..keep up the good work and keep coming up with such videos,and of course thanks a ton

[@i_DeepakV]

Very nicely explained, clarity in your voice. This code is easy to understand than GFG solution. Good job!

[@pratube4846]

Irony is that, this cannot be solved without sorting the array 😂

[@vivekshrivastav3674]

it can be done but that method will take O(n^2) time complexity. Selection sort

[@aj.anshuljohri]

@@vivekshrivastav3674 You can optimize the selection using map. I did this, it worked, and it's O(nlogn). int minSwaps(vector &num) { // Code here map mp; int ans = 0; int n = num.size(); for (int i = 0; i < n; i++) { //assigning index to its value mp[num[i]] = i; } for (int i = 0; i < n; i++) { //extracting minimum element auto pr = *mp.begin(); int mini_ele = pr.first; int mini_ele_ind = pr.second; if (mini_ele_ind != i) { //swapping current element index with //minimum element index mp[num[i]] = mini_ele_ind; swap(num[i], num[mini_ele_ind]); ans++; } //erasing the minimum element as it's processed mp.erase(mp.begin()); } return ans; }

[@barathnatarajan8566]

Beautiful explanation So clear!

[@rishukumarsingh3926]

I understood the approach, but i don't get that, what lead to this approach, what is the thought process behind appraching this question in this ways, when i was solving it, i made it complicated by observing dependencies of position in terms of graph!

[@adeeshsinghai7105]

LET CASE 1: Bhai agr kisi array ko sort krna h toh number of swaps btane hain. LET CASE 2: Maan le tune uss array ko sort kr diya ab tu chahta h uss array ko wapas se original array m convert krna . Dono case m swaps ka answer same hoga. BASS LOGIC YAHI H. TRACK KRTE JAA RAHE HAIN CORRECT POSITION KYA HONI CHAHIYE SORTED ARRAY MEIN

[@yuvrajagarkar8942]

thank you for putting so much efforts, worth the time 👍

[@vamshisamineniz5905]

good selection of questions

[@sougatoghosh8467]

such logics are hard to build. hatsoff

[@kennyackerman5429]

You look so gorgeous btw nice explanation ❤

[@ashokdurunde1814]

very nice explanation thank you very much

[@hardcash9930]

in which company are you placed now and with what approx package? (you are great motivation)

[@indiancyberclub]

nice explaination absolutely loved it❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

[@kaushikvelidandla7010]

Why is the result minimal ? That explanation is not clear. Might be better to explain using dependency graph and connected components

[@kanaramjangid8563]

Very nice

[@MritunjayKumar-rd2es]

this was the best explaination

[@sangamchoudhary6977]

fantastic 🔥

[@rishikeshmishra715]

Nice explanation !

[@piyushbhagwat3119]

Thank you!

[@techstuff9830]

How can we tackle this if duplicates are allowed?

[@somnathmore1082]

Thank you didi,clear my doubt

[@tit162-tiwarianurag2]

Explanation is good

[@kirankutte7073]

Will this appraoch work for if elements are from 0 - N-1

[@pk4288]

what if there are repeated elemets

[@debashishghosh4549]

Can somebody tell me the difference between the number of inversion count question and this one.

[@anshulkumarneekhara9377]

What is the intuition behind this approach??

[@manojnavinjamuri5867]

Thank you Alisha

[@AmanSharma-vb5jl]

🔥

[@systemforge]

Woah.. how to come up with ideas like this...

[@harshits-1195]

Can anybody Tell me What if there are duplicate elements in vector

[@shyren_more]

Thanks, but how can we claim this approach always guarantee the correct ans? Is there some intuition behind it?

[@anshulkumarneekhara9377]

correct. What is the intuition behind this approach??

[@abc-ym4zs]

madam i have one doubt when i have seen in solution in discussion section i am not able to understand but after watching your youtube solution i understood so why this happens i am always depending on yt videos how to overcome this i am not able to improve problem solving

[@dhananjoydey1337]

thanks

[@aryansiroyajain8503]

Let me just ignore it was the best part😄

[@shreyamaheshwari7329]

Mam how do we make sure its the minimum number of sorts which we had found

[@bhaskarmishra8479]

yeah... how do we guarantee that this would be the min no. of swaps

[@T_tintin]

I think it's probably the minimum no of swaps becoz we r sorting the array and we already know the correct positions of the elements and we r placing them there only . It's the best thing we can do .Put them where they should be with one swap only. And if they r already there don't swap.

[@rishabhgupta9846]

good video

[@smartwork7098]

Thanks

[@learnwithayush7838]

😍😍😍😍😍😍😍😍😍😍😍😍😍😍😍😍😍😍 Very Nice Explanation . And you are also very beutifull😁😁😁😁

[@Jitendrakumar-gb7cn]

I came here to see graph approach why using wrong thumbnail , but your approach is pretty much hint to the graph approach

[@alexrcrew1975]

one day her browser is gonna crash in between the tutorial .. so many tabs are opened haha

[@apk7373]

Use a better writing board like microsoft whiteboard or any similar... The one you are using is worse. But the explanation is amazing

[@deepakjainseth8126]

alisha aap 1x ke speed mey bola karo

[@Ninja-yt2qs]

Very confusing, no need to complex the simple things

[@prakashsingh1107]

Itna jldi bolti ho ki kuch smjh hi ni aata