LeetCode 3587 - Minimum Adjacent Swaps to Alternate Parity

The problem requires transforming a given array of distinct integers into an arrangement where the parity of adjacent elements alternates - that is, an even number must always be next to an odd number, and vice versa.

leetcodemediumarraygreedy

LeetCode Problem 3587

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem requires transforming a given array of distinct integers into an arrangement where the parity of adjacent elements alternates - that is, an even number must always be next to an odd number, and vice versa. The only allowed operation is swapping adjacent elements, and we need to compute the minimum number of such swaps required to achieve a valid alternating parity sequence. If it is impossible to form such a sequence, the result should be -1.

The input is a list of distinct integers, with the length up to 10^5. This constraint implies that O(n^2) solutions are too slow, so any brute-force approach trying all permutations is infeasible. The integers themselves can be as large as 10^9, but their exact values are irrelevant beyond their parity.

Important edge cases include arrays that are already valid, arrays that are impossible to rearrange into an alternating pattern due to parity imbalance, and arrays of length 1, which are trivially valid.

Approaches

A brute-force approach would attempt to generate all permutations of the array and check which ones satisfy alternating parity. For each valid permutation, we could then calculate the minimum number of adjacent swaps using an algorithm like bubble sort or inversion counting. While this would eventually find the correct answer, the factorial time complexity, O(n!), is completely impractical for the problem size (n <= 10^5).

The key insight for an efficient solution is that the only property that matters is parity, not the specific integer values. Therefore, we can focus on the positions of even and odd numbers. We can compute the minimum swaps by considering two possible valid target patterns: one starting with an even number, the other starting with an odd number. We then count the positions where evens and odds would need to move to match each target pattern. The minimum number of swaps can be derived from the sum of absolute differences between current positions and target positions, divided by 2 for adjacency swaps.

This works because adjacent swaps can effectively move a number to any position, and the minimum number of swaps for a sequence of moves is the sum of the distances in the target positions.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations and calculate swaps, infeasible for n ~ 10^5
Optimal O(n) O(n) Count parity positions, compute minimal adjacent swaps to match valid alternating patterns

Algorithm Walkthrough

  1. Separate positions by parity: Traverse the array and record the indices of even and odd numbers in two separate lists. This allows us to reason about which numbers need to move to which positions.
  2. Check feasibility: For a valid alternating sequence to exist, the counts of even and odd numbers must either be equal or differ by exactly 1. Otherwise, return -1 immediately.
  3. Define target patterns: Depending on which parity occurs more frequently (or either if counts are equal), generate two possible valid patterns: one where the first element is even, the other where the first element is odd.
  4. Calculate swap counts: For each valid pattern, calculate the number of swaps required to move numbers from their current positions to the target positions. Since only adjacent swaps are allowed, the number of swaps needed to move a number from index i to index j is abs(i - j).
  5. Return minimum: Out of the feasible patterns, return the pattern that requires the fewest swaps.

Why it works: The algorithm works because we focus only on parity and relative positions. By aligning the actual indices with the target indices, the sum of absolute differences divided by 2 gives the minimum number of adjacent swaps, since each swap moves a number closer by 1 index.

Python Solution

from typing import List

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        evens = [i for i, x in enumerate(nums) if x % 2 == 0]
        odds = [i for i, x in enumerate(nums) if x % 2 == 1]
        
        n = len(nums)
        if abs(len(evens) - len(odds)) > 1:
            return -1
        
        def count_swaps(target_parity: int) -> int:
            swaps = 0
            even_idx, odd_idx = 0, 0
            for i in range(n):
                if i % 2 == target_parity:
                    swaps += abs(evens[even_idx] - i)
                    even_idx += 1
                else:
                    swaps += abs(odds[odd_idx] - i)
                    odd_idx += 1
            return swaps
        
        if len(evens) > len(odds):
            return count_swaps(0) // 2
        elif len(odds) > len(evens):
            return count_swaps(1) // 2
        else:
            return min(count_swaps(0), count_swaps(1)) // 2

Implementation walkthrough: We first collect indices of evens and odds. Then we check feasibility based on counts. The helper function count_swaps computes the sum of distances for moving elements to a target pattern. Finally, we handle three scenarios: more evens, more odds, or equal counts, returning the minimal swaps needed divided by 2 since each swap moves a number one step.

Go Solution

func minSwaps(nums []int) int {
    evens := []int{}
    odds := []int{}
    n := len(nums)
    
    for i, num := range nums {
        if num % 2 == 0 {
            evens = append(evens, i)
        } else {
            odds = append(odds, i)
        }
    }
    
    if abs(len(evens) - len(odds)) > 1 {
        return -1
    }
    
    countSwaps := func(targetParity int) int {
        swaps := 0
        evenIdx, oddIdx := 0, 0
        for i := 0; i < n; i++ {
            if i % 2 == targetParity {
                swaps += abs(evens[evenIdx] - i)
                evenIdx++
            } else {
                swaps += abs(odds[oddIdx] - i)
                oddIdx++
            }
        }
        return swaps
    }
    
    if len(evens) > len(odds) {
        return countSwaps(0) / 2
    } else if len(odds) > len(evens) {
        return countSwaps(1) / 2
    } else {
        a := countSwaps(0)
        b := countSwaps(1)
        if a < b {
            return a / 2
        }
        return b / 2
    }
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Go-specific notes: Slices are used to store indices. Division by 2 is integer division, which is correct since the sum of absolute differences is always even when the array can be arranged in alternating parity. The helper function abs replaces Python's built-in abs.

Worked Examples

Example 1: nums = [2,4,6,5,7]

Indices: evens = [0,1,2], odds = [3,4]

Pattern starting with even: [0,1,2,3,4] → swaps = |0-0|+|1-2|+|2-4| + |3-1|+|4-3| = 0+1+2 + 2+1 = 6 → /2 = 3 swaps

Example 2: nums = [2,4,5,7]

Indices: evens = [0,1], odds = [2,3]

Pattern starting with even: swaps = |0-0| + |1-2| + |2-1| + |3-3| = 0+1+1+0 = 2 → /2 = 1 swap

Example 3: nums = [1,2,3]

Indices: evens = [1], odds = [0,2]

Pattern starting with odd: swaps = |0-0| + |1-1| + |2-2| = 0 → /2 = 0 swaps

Example 4: nums = [4,5,6,8]

Indices: evens = [0,2,3], odds = [1]

|3-1| > 1 → impossible → -1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to collect indices + single pass to compute swaps
Space O(n) Store indices of evens and odds

The algorithm scales linearly with the size of the input array, both in terms of time and space, which is optimal given the problem constraints.

Test Cases

# Provided examples
assert Solution().minSwaps([2,4,6,5,7]) == 3
assert Solution().minSwaps([2,4,5,7]) == 1
assert Solution().minSwaps([1,2,3]) == 0
assert Solution().minSwaps([4,5,6,8]) == -1

# Edge cases
assert Solution().minSwaps([1]) ==