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.
Good question. I failed due to timeout because I guessed that the correct solution is actually NP hard. So I did a recursive search. This worked on the samples, but is super slow on larger sets.
When half the submission test failed due to timeout I realized I'd need to settle for the solution implied by the description. That was much simpler and passed all tests.
The problem constraints should have clued me in that I need an O(n) solution, therefore not a tree search.
Note that the very first swap of the first example in the description involves a swap that does not put either element in it's home position, but instead sets up future moves to be "lucky" (putting both elements in home position). That doesn't fit the ordinary solution. Actually that's what got me into the depth first search.
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 →
Good question. I failed due to timeout because I guessed that the correct solution is actually NP hard. So I did a recursive search. This worked on the samples, but is super slow on larger sets.
When half the submission test failed due to timeout I realized I'd need to settle for the solution implied by the description. That was much simpler and passed all tests.
The problem constraints should have clued me in that I need an O(n) solution, therefore not a tree search.
Note that the very first swap of the first example in the description involves a swap that does not put either element in it's home position, but instead sets up future moves to be "lucky" (putting both elements in home position). That doesn't fit the ordinary solution. Actually that's what got me into the depth first search.