Minimum Adjacent Swaps to Alternate Parity solution and explanation
5 more videos on this problem
3587. Minimum Adjacent Swaps to Alternate Parity | Biweekly Contest 159 | Array | LeetcodeRapid Syntax · 14:53 · 1K views
LeetCode 3587. Minimum Adjacent Swaps to Alternate Parity | Greedy | Medium | TC O(N) && SC O(N)Leet's Code · 20:38 · 503 views
Leetcode contest Biweekly Contest 159 - Q1. Minimum Adjacent Swaps to Alternate ParityADevOpsEngineer · 9:29 · 364 views
3587. Minimum Adjacent Swaps to Alternate Parity (Leetcode Medium)Programming Live with Larry · 12:46 · 343 views
Minimum Adjacent Swaps to Alternate Parity | Leetcode 3587 | Biweekly Contest 159 | Java SolutionExpertFunda · 29:50 · 184 views
3587 - Minimum Adjacent Swaps to Alternate Parity | C++ Clean Code + LogicBEASTCODES · 16:33 · 162 views
The problem
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] <= 109- All elements in
numsare distinct.
Approach overview
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.
Solution
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.
class Solution:
def minSwaps(self, nums: List[int]) -> int:
def calc(k: int) -> int:
return sum(abs(i - j) for i, j in zip(range(0, len(nums), 2), pos[k]))
pos = [[], []]
for i, x in enumerate(nums):
pos[x & 1].append(i)
if abs(len(pos[0]) - len(pos[1])) > 1:
return -1
if len(pos[0]) > len(pos[1]):
return calc(0)
if len(pos[0]) < len(pos[1]):
return calc(1)
return min(calc(0), calc(1))class Solution {
private List<Integer>[] pos = new List[2];
private int[] nums;
public int minSwaps(int[] nums) {
this.nums = nums;
Arrays.setAll(pos, k -> new ArrayList<>());
for (int i = 0; i < nums.length; ++i) {
pos[nums[i] & 1].add(i);
}
if (Math.abs(pos[0].size() - pos[1].size()) > 1) {
return -1;
}
if (pos[0].size() > pos[1].size()) {
return calc(0);
}
if (pos[0].size() < pos[1].size()) {
return calc(1);
}
return Math.min(calc(0), calc(1));
}
private int calc(int k) {
int res = 0;
for (int i = 0; i < nums.length; i += 2) {
res += Math.abs(pos[k].get(i / 2) - i);
}
return res;
}
}class Solution {
public:
int minSwaps(vector<int>& nums) {
vector<int> pos[2];
for (int i = 0; i < nums.size(); ++i) {
pos[nums[i] & 1].push_back(i);
}
if (abs(int(pos[0].size() - pos[1].size())) > 1) {
return -1;
}
auto calc = [&](int k) {
int res = 0;
for (int i = 0; i < nums.size(); i += 2) {
res += abs(pos[k][i / 2] - i);
}
return res;
};
if (pos[0].size() > pos[1].size()) {
return calc(0);
}
if (pos[0].size() < pos[1].size()) {
return calc(1);
}
return min(calc(0), calc(1));
}
};function minSwaps(nums: number[]): number {
const pos: number[][] = [[], []];
for (let i = 0; i < nums.length; ++i) {
pos[nums[i] & 1].push(i);
}
if (Math.abs(pos[0].length - pos[1].length) > 1) {
return -1;
}
const calc = (k: number): number => {
let res = 0;
for (let i = 0; i < nums.length; i += 2) {
res += Math.abs(pos[k][i >> 1] - i);
}
return res;
};
if (pos[0].length > pos[1].length) {
return calc(0);
}
if (pos[0].length < pos[1].length) {
return calc(1);
}
return Math.min(calc(0), calc(1));
}func minSwaps(nums []int) int {
pos := [2][]int{}
for i, x := range nums {
pos[x&1] = append(pos[x&1], i)
}
if abs(len(pos[0])-len(pos[1])) > 1 {
return -1
}
calc := func(k int) int {
res := 0
for i := 0; i < len(nums); i += 2 {
res += abs(pos[k][i/2] - i)
}
return res
}
if len(pos[0]) > len(pos[1]) {
return calc(0)
}
if len(pos[0]) < len(pos[1]) {
return calc(1)
}
return min(calc(0), calc(1))
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Adjacent Swaps to Alternate Parity easy or hard?
Minimum Adjacent Swaps to Alternate Parity is typically classified as a Medium problem. The difficulty comes from recognizing that only two valid parity patterns exist and converting adjacent swap operations into index distance calculations.
Minimum Adjacent Swaps to Alternate Parity Python/Java solution
Most implementations iterate through the array, store indices of elements with a given parity, and calculate displacement relative to the expected alternating positions. The same greedy logic works across Python, Java, C++, Go, and TypeScript with linear time complexity.
How to solve Minimum Adjacent Swaps to Alternate Parity in O(n)?
Count the number of even and odd elements first. If their counts differ by more than one, alternating is impossible. Otherwise evaluate two patterns: even at index 0 or odd at index 0. For each pattern, sum the absolute difference between current indices of matching parity elements and their target indices. The smaller total is the minimum swaps.
What is the best approach for Minimum Adjacent Swaps to Alternate Parity?
The most efficient solution uses case analysis with a greedy placement strategy. Only two valid alternating patterns exist: even-first or odd-first. For each pattern, compute the cost of moving elements to the required parity positions using index differences. This runs in O(n) time and guarantees the minimum number of adjacent swaps.
Is Minimum Adjacent Swaps to Alternate Parity asked at Google/Amazon/Meta?
Parity arrangement and minimum adjacent swap problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include alternating binary arrays, grouping elements with minimum swaps, and rearranging arrays under adjacency constraints. The greedy index-distance technique is a common interview pattern.
What data structure is used in Minimum Adjacent Swaps to Alternate Parity?
The solution mainly uses arrays or lists to track indices of even and odd elements. No complex data structures are required. The algorithm relies on counting, index traversal, and simple arithmetic to compute adjacent swap distances.
What is the time complexity of Minimum Adjacent Swaps to Alternate Parity?
The optimal greedy approach runs in O(n) time because you scan the array once to collect parity positions and once to compute the swap cost. Space complexity is typically O(n) if you store indices of even or odd elements, though it can be reduced to O(1) with running counters.