[Java] Forced array swaps

Given a start and end array, generate a list of positions where to swap the 0 element in order to move all elements from start to end position with the following rules:

• elements can only be swapped with the 0, not between themselves
• each element can only appear once
• element 0 must be in the arrays
• there can be more than one way to obtain the desired swap, return any valid sequence

This exercise will easily tangle your brain with all those indexes flying around, so it's quite sure to make some small mistake while coding. Luckily testing and writing while testing on paper helps a lot to keep this in check.

The idea is simple: since we cannot swap elements between themselves, if we want to bring an element to a certain position, we must bring the 0 element there first, then swap it with the desired element.

While doing this, we always keep track of where did we move the 0 element, to generate our output.

Time and space complexity is O(N). As auxiliary structures we use a map from element to its current position; in this implementation we reuse the input array for our processing, but we could also easily copy it to a new array if we do not want to destroy the input, still keeping the space in O(N).

For processing, starting at index 0, we check if the elements in current (initially start) and end array match. If not, we swap the element at the current position with the element 0, then we check again and if the elements still do not match, we swap the 0 with the desired element before moving on to the next index.
Since we do at most 2 sets of constant operations (map gets and puts + list add + swaps) for each index, the total time is O(N).

Meanwhile, we always maintain our map updated and remember to track in another structure all the places where we moved the element 0.

You can check my implementation of forcedSwaps on my Gist alongside some test cases in ForcedSwapJTests.