You are given an array nums of distinct integers.
In one operation, you can swap any two adjacent elements in the array.
An arrangement of the array is considered valid if the parity of adjacent elements alternates, meaning every pair of neighboring elements consists of one even and one odd number.
Return the minimum number of adjacent swaps required to transform nums into any valid arrangement.
If it is impossible to rearrange nums such that no two adjacent elements have the same parity, return -1.
Example 1:
Input: nums = [2,4,6,5,7]
Output: 3
Explanation:
Swapping 5 and 6, the array becomes [2,4,5,6,7]
Swapping 5 and 4, the array becomes [2,5,4,6,7]
Swapping 6 and 7, the array becomes [2,5,4,7,6]. The array is now a valid arrangement. Thus, the answer is 3.
Example 2:
Input: nums = [2,4,5,7]
Output: 1
Explanation:
By swapping 4 and 5, the array becomes [2,5,4,7], which is a valid arrangement. Thus, the answer is 1.
Example 3:
Input: nums = [1,2,3]
Output: 0
Explanation:
The array is already a valid arrangement. Thus, no operations are needed.
Example 4:
Input: nums = [4,5,6,8]
Output: -1
Explanation:
No valid arrangement is possible. Thus, the answer is -1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109nums are distinct.Problem Overview: You are given an array of integers and need to rearrange it so that even and odd numbers strictly alternate. Only adjacent swaps are allowed. The task is to compute the minimum number of swaps required, or determine that it is impossible.
Approach 1: Brute Force Simulation (O(n2) time, O(1) space)
Simulate the process of fixing the array position by position. Decide the required parity for index i, then scan forward to find the nearest element with that parity and repeatedly swap it left until it reaches position i. Each move costs the number of adjacent swaps performed. Continue until the array alternates or a required parity cannot be found. This approach directly models the operation rules but becomes slow because each placement may require multiple swaps and repeated scans of the array.
Approach 2: Case Analysis + Greedy Positioning (O(n) time, O(n) space)
The key observation: the final array can start in only two valid patterns — even, odd, even, odd... or odd, even, odd, even.... First count how many even and odd numbers exist. If the difference between counts exceeds 1, forming an alternating array is impossible.
For each valid pattern, record the indices of numbers with the required parity (for example all even indices in the array). Then compute how many adjacent swaps are needed to move them to their target positions. Because swaps are adjacent, the minimum cost equals the sum of |current_index - target_index| for each element placed in order. Iterate through the array once to collect positions, then compute the distance cost for the target pattern.
This greedy method works because the optimal arrangement keeps elements in their relative order while shifting them to the nearest valid parity slot. Evaluating both starting patterns and taking the minimum gives the optimal answer.
Recommended for interviews: Case Analysis + Greedy is the expected solution. It reduces the problem to counting and index alignment, achieving O(n) time with a single pass. Interviewers typically look for the insight that only two valid alternating patterns exist and that adjacent swap cost equals index displacement. This problem combines counting from Array problems with positional reasoning common in Greedy algorithms.
For a valid arrangement, the number of odd and even numbers can only differ by 1 or be equal. Therefore, if the difference between the number of odd and even numbers is greater than 1, it is impossible to form a valid arrangement, and we should return -1 directly.
We use an array pos to store the indices of odd and even numbers, where pos[0] stores the indices of even numbers and pos[1] stores the indices of odd numbers.
If the number of odd and even numbers is equal, there are two valid arrangements: odd numbers before even numbers, or even numbers before odd numbers. We can calculate the number of swaps required for both arrangements and take the minimum.
If the number of odd numbers is greater than the number of even numbers, there is only one valid arrangement, which is odd numbers before even numbers. In this case, we only need to calculate the number of swaps for this arrangement.
Therefore, we define a function calc(k), where k indicates the parity of the first element (0 for even, 1 for odd). This function calculates the number of swaps needed to transform the current arrangement into a valid arrangement starting with k. We just need to iterate over the indices in pos[k] and sum the differences between each index and its position in the valid arrangement.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Adjacent Swap Simulation | O(n^2) | O(1) | Useful for understanding how adjacent swaps move elements and verifying correctness on small arrays. |
| Case Analysis + Greedy Position Matching | O(n) | O(n) | Best general solution. Evaluate even-first and odd-first patterns, compute index displacement cost, and choose the minimum. |
| Greedy with Running Target Indices | O(n) | O(1) | Optimized variant that tracks the next valid slot for each parity without storing all indices. |
3587. Minimum Adjacent Swaps to Alternate Parity | Biweekly Contest 159 | Array | Leetcode • Rapid Syntax • 1,910 views views
Watch 5 more video solutions →Practice Minimum Adjacent Swaps to Alternate Parity with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor