Coding

Minimum Adjacent Swaps to Make a Valid Array

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a 0-indexed integer array nums.

Swaps of adjacent elements are able to be performed on nums.

A valid array meets the following conditions:

The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array. Return the minimum swaps required to make nums a valid array.

**Input: **nums = [3,4,5,5,3,1] Output: 6 Explanation: Perform the following swaps:

Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5]. It can be shown that 6 swaps is the minimum swaps required to make a valid array.

Input: nums = [9] **Output: **0 Explanation: The array is already valid, so we return 0.

Consider the array **[7, 8, 2, 5, 9]. **What is the minimum number of swaps required to make it valid?

1 <= nums.length <= 105
1 <= **nums[i] **<= 105

cpp

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public int minimumSwaps(int[] nums) {
        // Your code goes here
    }
}

python

class Solution:
    def minimumSwaps(self, nums):
        # Your code goes here

javascript

class Solution {
    minimumSwaps(nums) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public int MinimumSwaps(int[] nums)
    {
        // Your code goes here
    }
}

func minimumSwaps(nums []int) int {
}

Stuck? Show a way to structure it+

01Derive the target valid ordering.
02Map each original item to its target position.
03Count inversions in that position sequence.
04Use a Fenwick tree or merge sort.
05Use 64-bit arithmetic for swaps.

Reference answer

Adjacent swaps are exactly inversions relative to the desired final order. First derive the valid target ordering from the problem's rule, including tie-breaking; then replace every element in the original array by its target rank. The minimum number of adjacent swaps needed to transform one distinct ordering into another is the inversion count of those ranks. Count inversions with a Fenwick tree by scanning from right to left: query how many smaller ranks have already appeared, add that amount, then insert the current rank. Coordinate-compress if values are large or duplicates need stable ranks. This is O(N log N) time and O(N) space, much faster than simulating swaps. Explain the target-order proof before coding; that is the hard part.

Then expect these follow-ups

How would merge-sort inversion counting differ?
Tests: alternatives
How do duplicates change rank assignment?
Tests: stability

Hiring now

Get the Meta interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question