Minimum Adjacent Swaps to Make a Valid Array

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 _theminimum swaps required to make _nums a valid array.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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.

Example 2:

1
2
3


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

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

Solution

Method 1 – Greedy Index Calculation

Intuition

To make the array valid, we need to move the smallest element to the leftmost position and the largest element to the rightmost position. The minimum swaps required are the sum of swaps needed to move the smallest to the front and the largest to the end, adjusting for overlap if they cross.

Approach

Find the index of the first occurrence of the minimum value (leftmost min).
Find the index of the last occurrence of the maximum value (rightmost max).
The swaps to move min to the front is its index.
The swaps to move max to the end is (n - 1 - index of max).
If min index is after max index, subtract 1 from the total swaps (since moving min shifts max left).
Return the total swaps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int n = nums.size();
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        int minIdx = 0, maxIdx = n-1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == minVal) { minIdx = i; break; }
        }
        for (int i = n-1; i >= 0; --i) {
            if (nums[i] == maxVal) { maxIdx = i; break; }
        }
        int swaps = minIdx + (n-1-maxIdx);
        if (minIdx > maxIdx) swaps--;
        return swaps;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func minimumSwaps(nums []int) int {
    n := len(nums)
    minVal, maxVal := nums[0], nums[0]
    minIdx, maxIdx := 0, n-1
    for i, v := range nums {
        if v < minVal { minVal = v; minIdx = i }
        if v > maxVal { maxVal = v; maxIdx = i }
    }
    for i := 0; i < n; i++ {
        if nums[i] == minVal { minIdx = i; break }
    }
    for i := n-1; i >= 0; i-- {
        if nums[i] == maxVal { maxIdx = i; break }
    }
    swaps := minIdx + (n-1-maxIdx)
    if minIdx > maxIdx { swaps-- }
    return swaps
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
        int minIdx = 0, maxIdx = n-1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < minVal) { minVal = nums[i]; minIdx = i; }
            if (nums[i] > maxVal) { maxVal = nums[i]; maxIdx = i; }
        }
        for (int i = 0; i < n; ++i) if (nums[i] == minVal) { minIdx = i; break; }
        for (int i = n-1; i >= 0; --i) if (nums[i] == maxVal) { maxIdx = i; break; }
        int swaps = minIdx + (n-1-maxIdx);
        if (minIdx > maxIdx) swaps--;
        return swaps;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun minimumSwaps(nums: IntArray): Int {
        val n = nums.size
        val minVal = nums.minOrNull()!!
        val maxVal = nums.maxOrNull()!!
        var minIdx = nums.indexOf(minVal)
        var maxIdx = nums.lastIndexOf(maxVal)
        var swaps = minIdx + (n-1-maxIdx)
        if (minIdx > maxIdx) swaps--
        return swaps
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def minimum_swaps(nums: list[int]) -> int:
    n = len(nums)
    min_val = min(nums)
    max_val = max(nums)
    min_idx = nums.index(min_val)
    max_idx = n - 1 - nums[::-1].index(max_val)
    swaps = min_idx + (n - 1 - max_idx)
    if min_idx > max_idx:
        swaps -= 1
    return swaps

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


impl Solution {
    pub fn minimum_swaps(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let min_val = *nums.iter().min().unwrap();
        let max_val = *nums.iter().max().unwrap();
        let min_idx = nums.iter().position(|&x| x == min_val).unwrap();
        let max_idx = nums.iter().rposition(|&x| x == max_val).unwrap();
        let mut swaps = min_idx + (n-1-max_idx);
        if min_idx > max_idx { swaps -= 1; }
        swaps as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    minimumSwaps(nums: number[]): number {
        const n = nums.length;
        const minVal = Math.min(...nums);
        const maxVal = Math.max(...nums);
        const minIdx = nums.indexOf(minVal);
        const maxIdx = nums.lastIndexOf(maxVal);
        let swaps = minIdx + (n-1-maxIdx);
        if (minIdx > maxIdx) swaps--;
        return swaps;
    }
}

Complexity

⏰ Time complexity: O(n)
- One pass to find min/max and their indices.
🧺 Space complexity: O(1)
- Only a few variables used.

Problem#

Examples#

Solution#

Method 1 – Greedy Index Calculation#

Intuition#

Approach#

Code#

Complexity#