Minimum Adjacent Swaps to Make a Valid Array

Minimum Adjacent Swaps to Make a Valid Array

What is this problem about?

The Minimum Adjacent Swaps to Make a Valid Array problem involves an array of integers. An array is considered "valid" if the smallest element is at the very first index (index 0) and the largest element is at the very last index. You need to calculate the minimum number of adjacent swaps to achieve this. Note that if there are multiple smallest or largest elements, you can pick any of them to move.

Why is this asked in interviews?

This is a great Minimum Adjacent Swaps to Make a Valid Array interview question for entry-level positions at Amazon. It tests a candidate's ability to calculate "Manhattan distance" in one dimension and their attention to detail regarding overlapping paths. It's a logic-heavy problem that doesn't require complex data structures but does require clear thinking about indices.

Algorithmic pattern used

The Greedy interview pattern is the way to go here.

1. Find the index of the first occurrence of the minimum element.
2. Find the index of the last occurrence of the maximum element.
3. The number of swaps to move the min to the front is min_index.
4. The number of swaps to move the max to the back is (N - 1) - max_index.
5. Critical Logic: If the min_index is greater than the max_index, the two elements will "cross" each other during the swaps. This saves you exactly one swap.

Example explanation

Consider array [3, 4, 5, 2].

1. Min is 2 at index 3. Max is 5 at index 2.
2. Swaps to move 2 to index 0: 3 swaps.
3. Swaps to move 5 to index 3: 3 - 2 = 1 swap.
4. Since min_index (3) > max_index (2), they will cross.
5. Total = 3 + 1 - 1 = 3. Sequence: [3, 4, 5, 2] -> [3, 4, 2, 5] -> [3, 2, 4, 5] -> [2, 3, 4, 5]. (Total 3 swaps).

Common mistakes candidates make

• Not picking the best indices: Picking the last min and the first max, which would require more swaps. You want the min closest to the start and the max closest to the end.
• Forgetting the "Cross" case: Adding the two distances without checking if the elements pass each other, leading to an answer that is 1 higher than the correct one.
• Using Bubble Sort: Trying to actually sort the array, which calculates total inversions rather than just moving two specific elements.

Interview preparation tip

Always look for "interaction" between your moves. In many Greedy coding problems, doing action A might make action B easier (or harder). Identifying the "crossing" saving in this problem shows that you are thinking about the process holistically.