2340. Minimum Adjacent Swaps to Make a Valid Array π
Description
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
Solutions
Solution 1: Maintain Index of Extremes + Case Analysis
We can use indices $i$ and $j$ to record the index of the first minimum value and the last maximum value in the array $\textit{nums}$, respectively. Traverse the array $\textit{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 $\textit{nums}$ is already a valid array, and no swaps are needed. Return $0$.
- If $i < j$, it means the minimum value in the array $\textit{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 $\textit{nums}$.
- If $i > j$, it means the minimum value in the array $\textit{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 $\textit{nums}$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|