To solve this problem efficiently, we store the each value and their positions into a HashMap. Then we pop off the largest value in the HashMap as we put it in the correct position of array while counting swaps along the way. Using a HashMap reduces the time complexity to linear time or O(n).
One important thing to keep in mind is that we must start from the highest item in the list because the question says “Any person in the queue can bribe the person directly in front of them to swap positions.”
A simple example would be the following case:
1 2 5 3 7 8 6 4 Here if we start from the smaller value, when we reach 4, it is 4 swaps away from its correct position. Thus resulting in a “Too chaotic” condition. Thus we need to start from 8. Which would give us the correct answer of 7.
