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.
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).
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 →
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).