Watch 6 video solutions for Minimum Adjacent Swaps to Alternate Parity, a medium level problem involving Array, Greedy. This walkthrough by Rapid Syntax has 1,910 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |