Skip to main content
Talentd

Minimum Adjacent Swaps to Alternate Parity - Solution & Explanation

MediumArrayGreedy11 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • All elements in nums are 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Adjacent Swap SimulationO(n^2)O(1)Useful for understanding how adjacent swaps move elements and verifying correctness on small arrays.
Case Analysis + Greedy Position MatchingO(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 IndicesO(n)O(1)Optimized variant that tracks the next valid slot for each parity without storing all indices.

Video Solution

3587. Minimum Adjacent Swaps to Alternate Parity | Biweekly Contest 159 | Array | Leetcode • Rapid Syntax • 1,983 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Adjacent Swaps to Alternate Parity with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays