3587. Minimum Adjacent Swaps to Alternate Parity

Difficulty: Medium

Topics: Array, Greedy Algorithm, Sorting

Companies: Google, Amazon, Microsoft

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 is valid if the parity of adjacent elements alternates (even-odd or odd-even). Return the minimum number of adjacent swaps required to transform nums into any valid arrangement. If impossible, return -1.

Example 1

Input: nums = [2,4,6,5,7]
Output: 3
Explanation: 
Swap 5 and 6: [2,4,5,6,7]
Swap 4 and 5: [2,5,4,6,7]
Swap 6 and 7: [2,5,4,7,6] (valid)

Example 2

Input: nums = [2,4,5,7]
Output: 1
Explanation: 
Swap 4 and 5: [2,5,4,7] (valid)

Example 3

Input: nums = [1,2,3]
Output: 0
Explanation: Already valid

Example 4

Input: nums = [4,5,6,8]
Output: -1
Explanation: No valid arrangement possible

Problem Link: View on LeetCode ↗

Key Insight

The solution relies on counting even/odd elements and pattern matching:

Count even and odd numbers - their counts must differ by at most 1
Two valid patterns: even-odd-even... or odd-even-odd...
For each valid pattern:
- Assign target positions to even/odd numbers
- Calculate inversion count to determine swap cost
Return the minimal swap cost between patterns

Why this works: The inversion count (number of out-of-order pairs) equals the minimum adjacent swaps needed to sort elements into their target positions.

Approach 1: Brute Force (For Small Inputs Only)

This approach generates all permutations of the array, checks for valid arrangements, and calculates the minimum adjacent swaps required for each valid permutation.

Algorithm Steps

Generate all permutations of the array
For each permutation:
- Check if adjacent elements have alternating parity
- Calculate adjacent swaps needed using bubble sort simulation
Return the minimum swaps found

Note: This approach is O(n!) and only practical for very small inputs (n ≤ 10)

Brute Force Solution

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int evenCount = 0, oddCount = 0;
        for (int num : nums) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        if (abs(evenCount - oddCount) > 1) return -1;
        
        vector<int> indices(n);
        for (int i = 0; i < n; i++) indices[i] = i;
        
        int minSwaps = INT_MAX;
        do {
            // Check if permutation has alternating parity
            bool valid = true;
            for (int i = 1; i < n; i++) {
                int a = nums[indices[i-1]];
                int b = nums[indices[i]];
                if ((a % 2) == (b % 2)) {
                    valid = false;
                    break;
                }
            }
            if (!valid) continue;
            
            // Calculate adjacent swaps to achieve this permutation
            vector<int> arr = indices;
            int swaps = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n - 1 - i; j++) {
                    if (arr[j] > arr[j+1]) {
                        swap(arr[j], arr[j+1]);
                        swaps++;
                    }
                }
            }
            minSwaps = min(minSwaps, swaps);
        } while (next_permutation(indices.begin(), indices.end()));
        
        return (minSwaps == INT_MAX) ? -1 : minSwaps;
    }
};

import java.util.*;

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int evenCount = 0, oddCount = 0;
        for (int num : nums) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        if (Math.abs(evenCount - oddCount) > 1) return -1;
        
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        
        int minSwaps = Integer.MAX_VALUE;
        do {
            // Check if permutation has alternating parity
            boolean valid = true;
            for (int i = 1; i < n; i++) {
                int a = nums[indices[i-1]];
                int b = nums[indices[i]];
                if (a % 2 == b % 2) {
                    valid = false;
                    break;
                }
            }
            if (!valid) continue;
            
            // Calculate adjacent swaps to achieve this permutation
            int[] arr = indices.clone();
            int swaps = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n - 1 - i; j++) {
                    if (arr[j] > arr[j+1]) {
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        swaps++;
                    }
                }
            }
            minSwaps = Math.min(minSwaps, swaps);
        } while (nextPermutation(indices));
        
        return (minSwaps == Integer.MAX_VALUE) ? -1 : minSwaps;
    }
    
    // Helper function to generate next permutation
    private boolean nextPermutation(int[] array) {
        int i = array.length - 1;
        while (i > 0 && array[i-1] >= array[i]) i--;
        if (i <= 0) return false;
        
        int j = array.length - 1;
        while (array[j] <= array[i-1]) j--;
        
        int temp = array[i-1];
        array[i-1] = array[j];
        array[j] = temp;
        
        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
        return true;
    }
}

from itertools import permutations

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        even_count = sum(1 for num in nums if num % 2 == 0)
        odd_count = n - even_count
        
        if abs(even_count - odd_count) > 1:
            return -1
            
        min_swaps = float('inf')
        indices = list(range(n))
        
        for perm in permutations(indices):
            # Check if permutation has alternating parity
            valid = True
            for i in range(1, n):
                a = nums[perm[i-1]]
                b = nums[perm[i]]
                if (a % 2) == (b % 2):
                    valid = False
                    break
                    
            if not valid:
                continue
                
            # Calculate adjacent swaps using bubble sort
            arr = list(perm)
            swaps = 0
            for i in range(n):
                for j in range(n-1-i):
                    if arr[j] > arr[j+1]:
                        arr[j], arr[j+1] = arr[j+1], arr[j]
                        swaps += 1
            min_swaps = min(min_swaps, swaps)
            
        return min_swaps if min_swaps != float('inf') else -1

Complexity: O(n! * n²) time, O(n) space - impractical for n > 10

Approach 2: Optimized Inversion Count

This efficient approach counts inversions to determine swap costs without brute-force permutation checks.

Algorithm Steps

Count parities: Calculate even and odd counts
Check feasibility: If |even - odd| > 1, return -1
Determine patterns:
- Pattern 1: Start with even (if even ≥ odd)
- Pattern 2: Start with odd (if odd ≥ even)
For each pattern:
- Assign target positions to even/odd numbers
- Calculate inversion count of position mapping
Return minimal inversion count between valid patterns

Optimal Solution

#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
private:
    // Merge sort helper to count inversions
    long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        long long inversions = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversions += (mid - i + 1);  // Count inversions
            }
        }
        
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        for (int idx = 0; idx < k; idx++) {
            arr[left + idx] = temp[idx];
        }
        
        return inversions;
    }

    long long mergeSortAndCount(vector<int>& arr, int left, int right) {
        long long inversions = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;
            inversions += mergeSortAndCount(arr, left, mid);
            inversions += mergeSortAndCount(arr, mid + 1, right);
            inversions += mergeAndCount(arr, left, mid, right);
        }
        return inversions;
    }
    
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int evenCount = 0, oddCount = 0;
        vector<int> evenIndices, oddIndices;
        
        // Count parities and record indices
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                evenCount++;
                evenIndices.push_back(i);
            } else {
                oddCount++;
                oddIndices.push_back(i);
            }
        }
        
        // Check feasibility
        if (abs(evenCount - oddCount) > 1) {
            return -1;
        }
        
        long long minSwaps = LONG_LONG_MAX;
        
        // Pattern 1: Start with even (even-odd-even...)
        if (evenCount >= oddCount) {
            vector<int> positions(n);
            // Assign even positions: 0, 2, 4,...
            for (int j = 0; j < evenIndices.size(); j++) {
                positions[evenIndices[j]] = 2 * j;
            }
            // Assign odd positions: 1, 3, 5,...
            for (int j = 0; j < oddIndices.size(); j++) {
                positions[oddIndices[j]] = 2 * j + 1;
            }
            minSwaps = min(minSwaps, mergeSortAndCount(positions, 0, n-1));
        }
        
        // Pattern 2: Start with odd (odd-even-odd...)
        if (oddCount >= evenCount) {
            vector<int> positions(n);
            // Assign odd positions: 0, 2, 4,...
            for (int j = 0; j < oddIndices.size(); j++) {
                positions[oddIndices[j]] = 2 * j;
            }
            // Assign even positions: 1, 3, 5,...
            for (int j = 0; j < evenIndices.size(); j++) {
                positions[evenIndices[j]] = 2 * j + 1;
            }
            minSwaps = min(minSwaps, mergeSortAndCount(positions, 0, n-1));
        }
        
        return minSwaps;
    }
};

import java.util.*;

class Solution {
    // Merge sort helper to count inversions
    private long mergeAndCount(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        long inversions = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversions += (mid - i + 1);  // Count inversions
            }
        }
        
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        
        for (int idx = 0; idx < temp.length; idx++) {
            arr[left + idx] = temp[idx];
        }
        
        return inversions;
    }

    private long mergeSortAndCount(int[] arr, int left, int right) {
        long inversions = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;
            inversions += mergeSortAndCount(arr, left, mid);
            inversions += mergeSortAndCount(arr, mid + 1, right);
            inversions += mergeAndCount(arr, left, mid, right);
        }
        return inversions;
    }

    public int minSwaps(int[] nums) {
        int n = nums.length;
        int evenCount = 0, oddCount = 0;
        List<Integer> evenIndices = new ArrayList<>();
        List<Integer> oddIndices = new ArrayList<>();
        
        // Count parities and record indices
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                evenCount++;
                evenIndices.add(i);
            } else {
                oddCount++;
                oddIndices.add(i);
            }
        }
        
        // Check feasibility
        if (Math.abs(evenCount - oddCount) > 1) {
            return -1;
        }
        
        long minSwaps = Long.MAX_VALUE;
        
        // Pattern 1: Start with even (even-odd-even...)
        if (evenCount >= oddCount) {
            int[] positions = new int[n];
            // Assign even positions: 0, 2, 4,...
            for (int j = 0; j < evenIndices.size(); j++) {
                positions[evenIndices.get(j)] = 2 * j;
            }
            // Assign odd positions: 1, 3, 5,...
            for (int j = 0; j < oddIndices.size(); j++) {
                positions[oddIndices.get(j)] = 2 * j + 1;
            }
            minSwaps = Math.min(minSwaps, mergeSortAndCount(positions, 0, n-1));
        }
        
        // Pattern 2: Start with odd (odd-even-odd...)
        if (oddCount >= evenCount) {
            int[] positions = new int[n];
            // Assign odd positions: 0, 2, 4,...
            for (int j = 0; j < oddIndices.size(); j++) {
                positions[oddIndices.get(j)] = 2 * j;
            }
            // Assign even positions: 1, 3, 5,...
            for (int j = 0; j < evenIndices.size(); j++) {
                positions[evenIndices.get(j)] = 2 * j + 1;
            }
            minSwaps = Math.min(minSwaps, mergeSortAndCount(positions, 0, n-1));
        }
        
        return (int) minSwaps;
    }
}

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        even_count = 0
        even_indices = []
        odd_indices = []
        
        # Count parities and record indices
        for i, num in enumerate(nums):
            if num % 2 == 0:
                even_count += 1
                even_indices.append(i)
            else:
                odd_indices.append(i)
                
        odd_count = n - even_count
        
        # Check feasibility
        if abs(even_count - odd_count) > 1:
            return -1
            
        def merge_sort_count(arr):
            if len(arr) <= 1:
                return 0
                
            mid = len(arr) // 2
            left_arr = arr[:mid]
            right_arr = arr[mid:]
            inversions = merge_sort_count(left_arr) + merge_sort_count(right_arr)
            
            i = j = k = 0
            while i < len(left_arr) and j < len(right_arr):
                if left_arr[i] <= right_arr[j]:
                    arr[k] = left_arr[i]
                    i += 1
                else:
                    arr[k] = right_arr[j]
                    j += 1
                    inversions += len(left_arr) - i
                k += 1
                
            while i < len(left_arr):
                arr[k] = left_arr[i]
                i += 1
                k += 1
                
            while j < len(right_arr):
                arr[k] = right_arr[j]
                j += 1
                k += 1
                
            return inversions
        
        min_swaps = float('inf')
        
        # Pattern 1: Start with even (even-odd-even...)
        if even_count >= odd_count:
            positions = [0] * n
            # Assign even positions: 0, 2, 4,...
            for j, idx in enumerate(even_indices):
                positions[idx] = 2 * j
            # Assign odd positions: 1, 3, 5,...
            for j, idx in enumerate(odd_indices):
                positions[idx] = 2 * j + 1
                
            count = merge_sort_count(positions.copy())  # Use copy to preserve original
            min_swaps = min(min_swaps, count)
            
        # Pattern 2: Start with odd (odd-even-odd...)
        if odd_count >= even_count:
            positions = [0] * n
            # Assign odd positions: 0, 2, 4,...
            for j, idx in enumerate(odd_indices):
                positions[idx] = 2 * j
            # Assign even positions: 1, 3, 5,...
            for j, idx in enumerate(even_indices):
                positions[idx] = 2 * j + 1
                
            count = merge_sort_count(positions.copy())
            min_swaps = min(min_swaps, count)
            
        return min_swaps

Complexity: O(n log n) time, O(n) space - efficient for large inputs

Approach Comparison

Approach	Time	Space	Best For
Brute Force	O(n! * n²)	O(n)	Small inputs (n ≤ 10)
Optimized Inversion	O(n log n)	O(n)	All cases (optimal)

Recommendation: Always use the inversion count approach for real-world problems

Edge Cases

1. Already valid arrangement

Input: [1,2,3] → Output: 0

2. Impossible arrangement

Input: [4,5,6,8] → Output: -1 (only even numbers)

3. Large input size

Input: [1,3,5,...,2,4,6,...] → Output: Calculated efficiently

4. Single element array

Input: [5] → Output: 0 (trivially valid)

Important: Always check the even/odd count difference first to avoid unnecessary computation

Frequently Asked Questions

Why do we need two patterns?

There are two possible valid arrangements: starting with even or starting with odd. We must compute costs for both and choose the minimal one when both are feasible.

How does the inversion count relate to adjacent swaps?

The inversion count (number of out-of-order pairs) directly equals the minimum adjacent swaps needed to sort elements. Each swap fixes exactly one inversion.

Why not use bubble sort to count swaps directly?

Bubble sort is O(n²) which is inefficient for large inputs (n=10^5). Merge sort inversion counting is O(n log n).

Can we use a Fenwick tree for inversion counting?

Yes, Fenwick trees can count inversions in O(n log n), but merge sort is simpler and equally efficient for this problem.

How do we handle arrays with duplicate values?

The problem states all elements are distinct, so we don't need to handle duplicates. For duplicates, we'd need stable sorting.

Why is the feasibility check important?

It avoids unnecessary computation. If |even - odd| > 1, no valid arrangement exists and we immediately return -1.

Can we solve with O(1) space?

No, we need O(n) space to store indices and position mappings. The merge sort recursion also uses O(log n) stack space.

What if the array has negative numbers?

Parity (even/odd) is defined for negative integers the same way as positives. The modulus operation works identically.

Why assign positions with 2*j and 2*j+1?

This creates a virtual target array where even and odd positions are interleaved. The exact values don't matter, only their relative ordering.

How does this preserve the relative order of elements?

We assign positions based on original indices, maintaining relative order within even and odd groups to minimize swaps.

Can we optimize further?

We could compute the inversion count without building the position array, but it wouldn't change the O(n log n) complexity.

Why use merge sort instead of quicksort?

Merge sort is stable and efficiently counts inversions during the merge process. Quicksort doesn't naturally count inversions.

How would you explain this to a beginner?

Imagine organizing books on a shelf: red covers (even) and blue covers (odd) must alternate. We first check if counts match (differ by ≤1), then calculate minimum adjacent swaps by tracking how far each book is from its ideal position.

Final Recommendation: The inversion count approach provides the optimal solution for this problem, efficiently handling large inputs while minimizing adjacent swaps.