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

[@intuitive_coder]

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

[@nayankhanna2367]

Great explanation & conceptual clarity!

[@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;
}

[@kaushikvelidandla7010]

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

[@sougatoghosh8467]

such logics are hard to build. hatsoff

[@yuvrajagarkar8942]

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

[@barathnatarajan8566]

Beautiful explanation
So clear!

[@studynewthings1727]

Very clear explanation.

[@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!

[@thewonderboy-k9x]

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

[@vamshisamineniz5905]

good selection of questions

[@sangamchoudhary6977]

fantastic 🔥

[@rishikeshmishra715]

Nice explanation !

[@hardcash9930]

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

[@Anonymous____________A721]

Microsoft
CTC 50lakhs

[@pk4288]

what if there are repeated elemets

[@MritunjayKumar-rd2es]

this was the best explaination

[@tit162-tiwarianurag2]

Explanation is good

[@piyushbhagwat3119]

Thank you!

[@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??

[@techstuff9830]

How can we tackle this if duplicates are allowed?

[@theabhishekparashar2]

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

[@kennyackerman5429]

You look so gorgeous btw nice explanation ❤

[@harsh7512]

tysm❣

[@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.

[@systemforge]

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

[@kirankutte7073]

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

[@learnwithayush7838]

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

[@sumit6586]

fr😭

[@ashokdurunde1814]

very nice explanation thank you very much

[@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

[@anshulkumarneekhara9377]

What is the intuition behind this approach??

[@SanyamBanoni]

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

[@somnathmore1082]

Thank you didi,clear my doubt

[@kanaramjangid8563]

Very nice

[@prathammittal6421]

do this method have a name ?
if it is pls tell the name

[@aryansiroyajain8503]

Let me just ignore it was the best part😄

[@dhananjoydey1337]

thanks

[@Jitendrakumar-gb7cn]

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

[@manojnavinjamuri5867]

Thank you Alisha

[@harshits-1195]

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

[@AmanSharma-vb5jl]

🔥

[@smartwork7098]

Thanks

[@rishabhgupta9846]

good video

[@debashishghosh4549]

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

[@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