We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Well I'm pretty new to algorithms also, but i'll do my best.
I think the simplest approach is (as demonstrated) to just step through element in the array in order, and check whether it matches our expected element.
For example, suppose you have an input array as given in the initial problem statement:
[7, 1, 3, 2, 4, 5, 6]
If you choose to sort it your expected order would be like this:
[1, 2, 3, 4, 5, 6, 7]
So basically just go through every element in the list - does 7 match our expected 1? If no, swap 7 with 1. Next we swap 7 with 2, etc.
If you think about it, that means in worst case the minimum amount of swaps needed for a given list with n elements will be n-1.
For example, consider the following list:
[7, 4, 2, 6, 1, 5, 3]
As this is a worst case scenario (all elements out of order), so the minimum number of swaps will be 6 here. Best way is to try by hand yourself and see if you can get the list ordered in fewer number of swaps - if the answer is no, then my impression would be that iterating over each element and checking whether it has an expected value is the simplest solution possible (really no algorithm involved in that case)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Swaps 2
You are viewing a single comment's thread. Return to all comments →
Well I'm pretty new to algorithms also, but i'll do my best.
I think the simplest approach is (as demonstrated) to just step through element in the array in order, and check whether it matches our expected element.
For example, suppose you have an input array as given in the initial problem statement: [7, 1, 3, 2, 4, 5, 6]
If you choose to sort it your expected order would be like this: [1, 2, 3, 4, 5, 6, 7]
So basically just go through every element in the list - does 7 match our expected 1? If no, swap 7 with 1. Next we swap 7 with 2, etc.
If you think about it, that means in worst case the minimum amount of swaps needed for a given list with n elements will be n-1.
For example, consider the following list: [7, 4, 2, 6, 1, 5, 3]
As this is a worst case scenario (all elements out of order), so the minimum number of swaps will be 6 here. Best way is to try by hand yourself and see if you can get the list ordered in fewer number of swaps - if the answer is no, then my impression would be that iterating over each element and checking whether it has an expected value is the simplest solution possible (really no algorithm involved in that case)