Minimum Adjacent Swaps to Make a Valid Array - Solution & Explanation

Problem Overview: You are given an integer array. A valid array means the smallest element appears at the beginning and the largest element appears at the end. The only operation allowed is swapping adjacent elements. The task is to compute the minimum number of adjacent swaps needed to reach that state.

Approach 1: Simulate Adjacent Swaps (Brute Force) (Time: O(n^2), Space: O(1))

A direct way is to simulate the process using adjacent swaps. First find the index of the smallest element and repeatedly swap it left until it reaches index 0. Then find the index of the largest element and swap it right until it reaches index n-1. Each swap shifts the element by one position. This approach works but can require up to O(n) swaps for each movement, leading to O(n^2) time in the worst case. It’s useful for understanding how adjacent swaps change positions but is inefficient for large arrays.

Approach 2: Maintain Index of Extremes + Case Analysis (Greedy) (Time: O(n), Space: O(1))

The optimal solution avoids simulation entirely. Scan the array once to record two values: the index of the leftmost minimum element and the index of the rightmost maximum element. Moving the minimum to the front requires exactly minIndex adjacent swaps. Moving the maximum to the end requires (n - 1 - maxIndex) swaps.

A small interaction between these two operations creates one edge case. If the maximum element originally appears before the minimum element (maxIndex < minIndex), shifting the minimum left will push the maximum one position to the right. That reduces the swaps needed for the maximum by one. The final formula becomes:

swaps = minIndex + (n - 1 - maxIndex)

If maxIndex < minIndex, subtract one additional swap.

This greedy observation turns a swap simulation into simple index arithmetic. The algorithm performs a single linear scan and constant-time math, making it very efficient. The logic relies on properties of array traversal and a small greedy insight: always move the smallest left and the largest right using the minimal required swaps.

Recommended for interviews: The greedy index-tracking approach is what interviewers expect. Mentioning the brute-force swap simulation shows you understand how adjacent swaps behave, but recognizing that the swap count equals distance to the boundaries demonstrates stronger problem-solving and leads to the optimal O(n) solution.