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):

1. You have to sort the array in both ascending and descending order as both will yield a minimum sum.
2. 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).
3. 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).

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!