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.
I read this part of the description "we can swap adjacent elements" to mean that swaps can only be a distance of 1. So 2 1 3 1 2 requires the 3 to move 2 times backwards and the front 2 to move back 2 spots. for a total of 4 moves. In fact, I solved it the "wrong" way by counting and summing the number of elements found so far that are larger then arr[i]. That is adding up 0, 1, 0, 2, 1 for the number of elements to the left that are greater. Also 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
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
I read this part of the description "we can swap adjacent elements" to mean that swaps can only be a distance of 1. So 2 1 3 1 2 requires the 3 to move 2 times backwards and the front 2 to move back 2 spots. for a total of 4 moves. In fact, I solved it the "wrong" way by counting and summing the number of elements found so far that are larger then arr[i]. That is adding up 0, 1, 0, 2, 1 for the number of elements to the left that are greater. Also O (n log n)