Minimum Adjacent Swaps to Make a Valid Array

Minimum Adjacent Swaps to Make a Valid Array - Problem

Array Greedy Medium

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 & Output

Example 1 — Basic Case

$ Input: nums = [3,4,5,5,2]

› Output: 6

💡 Note: Min element is 2 at index 4, needs 4 swaps to reach index 0. Max element is 5 at index 3, needs 2 swaps to reach index 4. Total: 4+2=6 swaps.

Example 2 — Elements Cross

$ Input: nums = [9]

› Output: 0

💡 Note: Single element array is already valid, no swaps needed.

Example 3 — Min Right of Max

$ Input: nums = [2,4,1,3]

› Output: 3

💡 Note: Min(1) at index 2 needs 2 swaps left. Max(4) at index 1 needs 2 swaps right. They cross, so total: 2+2-1=3 swaps.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [3,4,5,5,2] - min=2 at index 4, max=5 at index 3

Calculate Moves

Min needs 4 swaps left, max needs 2 swaps right

Final Result

Total 6 adjacent swaps needed

Key Takeaway

🎯 Key Insight: Calculate distances mathematically - no need to simulate the actual swapping process

Asked in

M Microsoft 25 G Google 20 a Amazon 15

The key insight is to calculate exact distances without simulation. Find the leftmost minimum and rightmost maximum positions, calculate swaps needed for each to reach target positions, and subtract 1 if they cross paths during movement. Best approach uses direct calculation in O(n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Direct Position Calculation	O(n)	O(1)	Calculate exact number of swaps needed without simulation
Brute Force Simulation	O(n²)	O(1)	Repeatedly find and swap elements until array becomes valid

Direct Position Calculation — Algorithm Steps

Find leftmost min and rightmost max positions
Calculate swaps for min to reach position 0
Calculate swaps for max to reach last position
Subtract 1 if min and max cross each other

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Positions

Locate leftmost min and rightmost max

Calculate Distance

Count moves needed for each element

Handle Crossing

Subtract 1 if elements cross paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n <= 1) return 0;
    
    int minVal = nums[0], maxVal = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    
    // Find leftmost occurrence of minimum
    int minPos = -1;
    for (int i = 0; i < n; i++) {
        if (nums[i] == minVal) {
            minPos = i;
            break;
        }
    }
    
    // Find rightmost occurrence of maximum
    int maxPos = -1;
    for (int i = n-1; i >= 0; i--) {
        if (nums[i] == maxVal) {
            maxPos = i;
            break;
        }
    }
    
    // Calculate swaps needed
    int swapsForMin = minPos;
    int swapsForMax = (n - 1) - maxPos;
    
    int totalSwaps = swapsForMin + swapsForMax;
    
    // If min is to the right of max, they will cross during swapping
    if (minPos > maxPos) {
        totalSwaps -= 1;
    }
    
    return totalSwaps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to find min and max positions

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for positions and calculations

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Position Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler