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.
Finally solved it! Spent some time trying to figure out the hidden details. Would appreciate if there had been another test case. Things i learnt - Java specifics (might be useful if you're stuck):
You have to sort the array in both ascending and descending order as both will yield a minimum sum.
Remember to use a LinkedHashMap (if you are using one) and not a HashMap to store the element key and index value (to preserve insertion order).
A copy of an ArrayList is a shallow copy. You need to addAll(originalArray) to create another array with the same values as the originalArray.
The algorithm is pretty simple: (just a brief run-through
, note the details, figure out the implementation)
compare every element of original array with a copy of the sorted array (refer 3)
when there's a mismatch, swap elements into their respective positions
count the total number of swaps
repeat the above with the array reversed (refer 1)
use a hashmap as a cache/lookup to speed things up O(1) (refer 2).
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
Finally solved it! Spent some time trying to figure out the hidden details. Would appreciate if there had been another test case. Things i learnt - Java specifics (might be useful if you're stuck):
addAll(originalArray)
to create another array with the same values as the originalArray.The algorithm is pretty simple: (just a brief run-through , note the details, figure out the implementation)
Example:
7 3 0 4 1 6 5 2 - original array
0 1 2 3 4 5 6 7 - sorted array
0 3 7 4 1 6 5 2 - after first swap
0 1 7 4 3 6 5 2 - after second swap
0 1 2 4 3 6 5 7 - after third swap
0 1 2 3 4 6 5 7 - after fourth swap
0 1 2 3 4 5 6 7 - after fifth swap
Did you notice the pattern? All the best!