LeetCode 2340. Minimum Adjacent Swaps to Make a Valid Array Solution in Java, C++, Python & More | Explanation + Code

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 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).

PythonJavaC++GoTypeScript

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)(code-box)

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); } }(code-box)

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); } };(code-box)

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 }(code-box)

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); }(code-box)