Minimum Swaps to Sort Array By Parity

Overview

The goal is to move all even numbers to the beginning of the array and all odd numbers to the end using the minimum number of swaps.

The key insight is identifying placement errors. In any valid final arrangement, the first $k$ indices (where $k$ is the total count of even numbers in the array) must contain all the even numbers. Any odd number currently occupying one of these first $k$ slots is "out of place." Since every swap can, at best, fix two misplaced elements (one odd element in the even section and one even element in the odd section), the minimum number of swaps is simply the count of even numbers that are currently sitting in positions that should belong to odd numbers (or vice versa).

Brute Force

A brute force approach involves simulating the process of finding a misplaced even number and a misplaced odd number, then swapping them until the array is partitioned correctly. We can iterate through the first $k$ elements (where $k$ is the count of evens) and, whenever we find an odd number, search the rest of the array (from $k$ to $n-1$) for an even number to swap it with.

def minSwapsToParity(nums: list[int]) -> int:
    n = len(nums)
    # Count how many even numbers exist to find the boundary
    even_count = sum(1 for x in nums if x % 2 == 0)
    
    swaps = 0
    # The first 'even_count' elements should be even
    for i in range(even_count):
        if nums[i] % 2 != 0:
            # Find an even number in the 'odd' section to swap with
            for j in range(even_count, n):
                if nums[j] % 2 == 0:
                    nums[i], nums[j] = nums[j], nums[i]
                    swaps += 1
                    break
    return swaps

• Time complexity: O(N^2) — In the worst case, for every odd number in the even prefix, we scan the entire suffix to find an even number.
• Space complexity: O(1) — We perform the swaps in-place without using extra data structures.

Optimal / Best Approach

The optimal approach recognizes that we don't actually need to perform the swaps. We only need to count how many even numbers are currently in the "wrong" half of the array.

1. First, count the total number of even integers in the array. Let this be k.
2. In the target state, these k even integers will occupy indices 0 to k - 1.
3. Iterate through the array from index 0 to k - 1.
4. Count how many odd numbers are currently occupying these slots.
5. Each such odd number must be swapped with an even number located somewhere in the range k to n - 1. Therefore, the count of these misplaced odd numbers is exactly the minimum number of swaps required.

def minSwapsToParity(nums: list[int]) -> int:
    # Step 1: Count total even numbers
    even_count = 0
    for x in nums:
        if x % 2 == 0:
            even_count += 1
            
    # Step 2: Count how many odd numbers are in the first 'even_count' positions
    misplaced_odds = 0
    for i in range(even_count):
        if nums[i] % 2 != 0:
            misplaced_odds += 1
            
    return misplaced_odds

• Time complexity: O(N) — We make two linear passes over the array (one to count total evens, one to count misplaced items).
• Space complexity: O(1) — We only store a few integer variables regardless of input size.

Why This Works

This problem is a specific case of the Partition logic used in Quicksort. Because we only care about parity (a binary state), any swap between an "odd-in-even-zone" and an "even-in-odd-zone" resolves two misplaced elements at once. Since the total number of even slots is fixed, for every odd number in the even zone, there must be a corresponding even number in the odd zone. Swapping them is the most efficient way to reach the target state, making the count of misplaced elements in one partition equal to the minimum swaps.

Fast