Minimum Adjacent Swaps to Make a Valid Array solution and explanation
9 more videos on this problem
2340. Minimum Adjacent Swaps to Make a Valid Array - LeetCode Python SolutionCode with Carter · 12:07 · 2K views
leetcode 2340 min adjacent swaps to make valid array c++ solutionleetcode blind 75 · 3:44 · 1K views
Leetcode 2340. Minimum Adjacent Swaps to Make a Valid Array - simple countingCode-Yao · 9:11 · 1K views
2340. Minimum Adjacent Swaps to Make a Valid Array (Leetcode Medium)Programming Live with Larry · 5:14 · 859 views
Minimum Adjacent Swaps to Make a Valid ArrayAmit K · 10:25 · 643 views
2340. Minimum Adjacent Swaps to Make a Valid ArrayJust Coding, with Jie · 5:54 · 277 views
LeetCode 2340. Minimum Adjacent Swaps to Make a Valid Array | Amazon Spring '23 High FrequencySoftware Interviews Prep · 13:21 · 252 views
🔥Leetcode 2340.Minimum Adjacent Swaps to Make a Valid Array #amazon #meta in last 1 month interviewsAccelerateAI Careers · 11:53 · 221 views
Leetcode 2340. Minimum Adjacent Swaps to Make a Valid Array (greedy)LetsCode · 9:13 · 53 views
Leetcode 2340. Minimum Adjacent Swaps to Make a Valid Array | বাংলা সমাধানLeetcode বাংলা · 11:52 · 38 views
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.
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 <= 1051 <= 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 arraynumsis already a valid array, and no swaps are needed. Return0. - If
i < j, it means the minimum value in the arraynumsis to the left of the maximum value. The number of swaps needed isi + n - 1 - j, wherenis the length of the arraynums. - If
i > j, it means the minimum value in the arraynumsis to the right of the maximum value. The number of swaps needed isi + 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).
class Solution:
def minimumSwaps(self, nums: List[int]) -> int:
i = j = 0
for k, v in enumerate(nums):
if v < nums[i] or (v == nums[i] and k < i):
i = k
if v >= nums[j] or (v == nums[j] and k > j):
j = k
return 0 if i == j else i + len(nums) - 1 - j - (i > j)class Solution {
public int minimumSwaps(int[] nums) {
int n = nums.length;
int i = 0, j = 0;
for (int k = 0; k < n; ++k) {
if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
i = k;
}
if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
j = k;
}
}
if (i == j) {
return 0;
}
return i + n - 1 - j - (i > j ? 1 : 0);
}
}class Solution {
public:
int minimumSwaps(vector<int>& nums) {
int n = nums.size();
int i = 0, j = 0;
for (int k = 0; k < n; ++k) {
if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
i = k;
}
if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
j = k;
}
}
if (i == j) {
return 0;
}
return i + n - 1 - j - (i > j);
}
};function minimumSwaps(nums: number[]): number {
let i = 0;
let j = 0;
const n = nums.length;
for (let k = 0; k < n; ++k) {
if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
i = k;
}
if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
j = k;
}
}
return i == j ? 0 : i + n - 1 - j - (i > j ? 1 : 0);
}func minimumSwaps(nums []int) int {
var i, j int
for k, v := range nums {
if v < nums[i] || (v == nums[i] && k < i) {
i = k
}
if v > nums[j] || (v == nums[j] && k > j) {
j = k
}
}
if i == j {
return 0
}
if i < j {
return i + len(nums) - 1 - j
}
return i + len(nums) - 2 - j
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Adjacent Swaps | O(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 |
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.