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.
To improve the performance - search complexity should be improved. Usual swap sorts have "n^2" complexity. Think about preparing some sorted array with faster complexity, "n* log n" should be ok. Then prepare some kind of map of the sorted array as a key and the original index in the given array as a value.
That allows making swaps on the next stage with "n" complexity.
This solution is not optimal in case of memory usage, but for this kind of task should be okay.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
To improve the performance - search complexity should be improved. Usual swap sorts have "n^2" complexity. Think about preparing some sorted array with faster complexity, "n* log n" should be ok. Then prepare some kind of map of the sorted array as a key and the original index in the given array as a value. That allows making swaps on the next stage with "n" complexity. This solution is not optimal in case of memory usage, but for this kind of task should be okay.