#3587

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Adjacent Swaps to Alternate Parity

Compute the minimum adjacent swaps to make array elements alternate between even and odd using greedy and invariant checks.

array greedy

Problem Statement

Given an array of distinct integers, you can swap any two adjacent elements. The goal is to reorder the array so that even and odd numbers strictly alternate.

Return the minimum number of adjacent swaps required to achieve this arrangement. If it is impossible to alternate parity, return -1. Arrays can be large, so consider efficient counting and greedy placement strategies.

Examples

Example 1

Input: nums = [2,4,6,5,7]

Output: 3

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

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

The array is already a valid arrangement. Thus, no operations are needed.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
All elements in nums are distinct.

Solution Approach

Count Parity and Validate

Compute the number of even and odd elements. If their counts differ by more than one, return -1 immediately, since alternating parity is impossible. This step ensures invariant validation before any swaps.

Greedy Placement for Minimum Swaps

Iterate through the array and for each position, place the correct parity element. Count the swaps needed to move misplaced elements to their target positions. Use separate counts for starting with even or odd to find the minimum.

Select Optimal Start

If counts are equal, try both starting with even and starting with odd, and choose the arrangement with fewer swaps. If counts are unequal, start with the parity that has more elements to satisfy alternating constraints efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to count parity and compute swaps since each element is visited once for position correction. Space complexity is O(1) extra if counting in place or O(n) if storing positions separately.

What Interviewers Usually Probe

Check parity counts first; mismatched counts indicate impossible arrangement.
Consider greedy placement: always move the nearest correct parity element to the current position.
Evaluate both starting options when counts are equal to ensure minimal swaps.

Common Pitfalls or Variants

Common pitfalls

Ignoring the case where abs(evenCnt - oddCnt) > 1 and attempting swaps unnecessarily.
Counting swaps incorrectly by assuming all elements can move freely instead of adjacent swaps only.
Not checking both starting parity options when counts are equal, leading to suboptimal swap count.

Follow-up variants

Allow swaps between any two elements, not just adjacent ones, which changes the minimal swap calculation.
Require the array to alternate parity but allow repeated numbers, which changes the invariant check.
Count swaps to alternate parity for multiple arrays in a batch, needing efficient cumulative computation.

FAQ

What is the main strategy for Minimum Adjacent Swaps to Alternate Parity?

The main strategy is to count even and odd elements, validate feasibility, and then greedily swap misplaced elements to alternate parity.

Can this problem be solved without counting parity first?

Skipping the parity count can lead to unnecessary computations or incorrect results, since an impossible arrangement might be attempted.

Why do we consider both starting with even and odd?

When counts are equal, trying both starting options ensures we find the minimal number of adjacent swaps.

How does the greedy approach work for adjacent swaps?

It moves the nearest correct parity element to its target position step by step, counting each swap to minimize total operations.

What is a common mistake when implementing this solution?

A common mistake is assuming swaps can be done with any distance instead of only adjacent elements, which underestimates required moves.

terminal

Solution

Solution 1: Case Analysis + Greedy

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#3588 find maximum area of a triangle #3576 transform array to all equal elements #3572 maximize ysum by picking a triplet of distinct xvalues