Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeArrayGreedy9 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

 

Example 1:

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: 
Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0.

 

Constraints:

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

Approach Overview

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.

Solution

We can use indices i and j to record the index of the first minimum value and the last maximum value in the array nums, respectively. Traverse the array nums to update the values of i and j.

Next, we need to consider the number of swaps.

  • If i = j, it means the array nums is already a valid array, and no swaps are needed. Return 0.
  • If i < j, it means the minimum value in the array nums is to the left of the maximum value. The number of swaps needed is i + n - 1 - j, where n is the length of the array nums.
  • If i > j, it means the minimum value in the array nums is to the right of the maximum value. The number of swaps needed is i + n - 1 - j - 1.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Adjacent SwapsO(n^2)O(1)For conceptual understanding of how adjacent swaps shift elements step-by-step
Maintain Index of Extremes + Case Analysis (Greedy)O(n)O(1)Optimal solution for interviews and production; requires only one array scan

Video Solution

2340. Minimum Adjacent Swaps to Make a Valid Array - LeetCode Python Solution • Code with Carter • 2,687 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Adjacent Swaps to Make a Valid Array easy or hard?
The problem is rated Medium because the logic is simple but the edge case between the minimum and maximum positions can be missed. Recognizing the index interaction and avoiding full swap simulation is the key insight.
Minimum Adjacent Swaps to Make a Valid Array Python/Java solution
In Python or Java, iterate through the array to track the smallest element's index and the largest element's index. Compute swaps using minIndex + (n - 1 - maxIndex) and subtract one if maxIndex < minIndex. The implementation is short and runs in O(n) time with O(1) extra space.
How to solve Minimum Adjacent Swaps to Make a Valid Array in O(n)?
Scan the array once to record the index of the smallest element (use the leftmost occurrence) and the largest element (use the rightmost occurrence). Compute swaps needed to move the minimum to index 0 and the maximum to index n-1. If the maximum index is less than the minimum index, subtract one because moving the minimum shifts the maximum right.
What is the best approach for Minimum Adjacent Swaps to Make a Valid Array?
The best approach tracks the index of the leftmost minimum element and the rightmost maximum element in one pass. The swaps needed are minIndex + (n - 1 - maxIndex), with a minus one adjustment if the maximum appears before the minimum. This greedy observation produces an O(n) time and O(1) space solution.
Is Minimum Adjacent Swaps to Make a Valid Array asked at Google/Amazon/Meta?
This style of problem appears in interviews at large tech companies because it tests array traversal, greedy reasoning, and edge‑case analysis. Variations of adjacent swap counting and index manipulation have been reported in interview prep sets used by companies like Amazon and Google.
What data structure is used in Minimum Adjacent Swaps to Make a Valid Array?
The problem primarily uses a simple array traversal with constant extra variables. No advanced data structures are required. The key idea is tracking indices of extreme values and applying greedy reasoning to compute the minimal number of adjacent swaps.
What is the time complexity of Minimum Adjacent Swaps to Make a Valid Array?
The optimal solution runs in O(n) time because the array is scanned once to locate the minimum and maximum indices. Only constant-time arithmetic is performed afterward. Space complexity is O(1) since no additional data structures are required.

Ready to solve this problem?

Practice Minimum Adjacent Swaps to Make a Valid Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Adjacent Swaps for K Consecutive Ones