HackerRank New Year Chaos: arriving at a given list using neighbor swaps
Good attempt, but unfortunately the nested loop brings the time complexity to O(n2). Keep in mind that .find performs a linear search on the vector, inspecting up to the entire array to find an element. We can arrive at a O(n) solution by exploiting the fact that no more than 2 swaps can be performed by any given element, which is a red flag in the problem statement that your solution ignores. In other words, we can transform the linear operation inside the array to constant time.

Here's the approach I used:

Start at the back of the array and move forward. For each element q[i] not in its original location, check only q[i-1] and q[i-2] to see if it moved to one of those locations. If the element is in q[i-1], then it must have used only one bribe. If at q[i-2], it must have taken two bribes to get there. Either way, perform an un-swap to return it to its original location. If it's not at either element, the array is "Too chaotic".

Let's try this algorithm on the input examples:

Example 1

initial state: 
[2, 1, 5, 3, 4]

[2, 1, 5, 3, 4]
             ^-- This element should be a 5. Let's look for 5 at index 3 or 2.
[2, 1, 5, 3, 4]
       ^-------- Found 5 at index 2. It must have swapped twice; set `bribes = 2`.
[2, 1, 3, 4, 5]
             ^-- Put 5 where it belongs by undoing the swaps it made.

[2, 1, 3, 4, 5]
          ^-- Moving to the next element, we see 4 is OK.

[2, 1, 3, 4, 5]
       ^-- Moving to the next element, we see 3 is OK.

[2, 1, 3, 4, 5]
    ^-- Moving to the next element, this element should be 2.
[2, 1, 3, 4, 5]
 ^----- Found 2. It must have swapped once; set `bribes = 3`.
[1, 2, 3, 4, 5]
    ^-- Put 2 where it belongs by undoing the swap it made.

Outcome: 3 bribes in total must have happened.


Example 2

initial state:
[2, 5, 1, 3, 4]

[2, 5, 1, 3, 4]
             ^-- This element should be 5. Let's find 5.
[2, 5, 1, 3, 4]
          ^----- This element, q[i-1], is not 5.
[2, 5, 1, 3, 4]
       ^-------- This element, q[i-2], is not 5, either.

Outcome: Too chaotic! 5 must have used more than 2 
         bribes to get any further than index 2.