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.

Description Hints 2 Solution Video 12:07

2340. Minimum Adjacent Swaps to Make a Valid Array

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Medium72.6% acceptance1 companyPremium elsewhere, free here

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 3^rd and 4^th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4^th and 5^th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3^rd and 4^th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2^nd and 3^rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1^st and 2^nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0^th and 1^st 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 <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Amazon

Topics

Array Greedy

Hints open one at a time

Hint 1

Notice that in order to obtain the minimum swaps, we should focus on the smallest element that is the leftmost and the largest element that is the rightmost.

Hint 2

We can take those elements and greedily only do swaps that bring them closer to their respective end positions.

12:07

Still stuck?Read the written solution, or watch a walkthrough.

Open solution