Minimum swaps to put evens before odds

What the target looks like. Let E be the number of even values in nums. In any valid final arrangement, indices 0 .. E-1 hold exactly the evens and indices E .. n-1 hold exactly the odds. The order inside each block does not matter, so the only thing to fix is which parity sits in each slot.

Counting misplaced elements. Call an odd value inside the first E slots a misplaced odd, and an even value in the last n - E slots a misplaced even. The first block has E slots and the array has E evens in total, so every odd that steals a front slot pushes exactly one even to the back. The two counts are always equal; call it k.

Lower bound. One swap changes the contents of two slots. To reduce the number of misplaced odds it must move an odd out of the front block, and the only useful partner is a misplaced even in the back block. Any single swap fixes at most one misplaced odd. So at least k swaps are needed.

Upper bound. Pair the i-th misplaced odd with the i-th misplaced even and swap each pair. Each swap fixes one of each, so k swaps are enough. Therefore the answer is exactly k, the number of odd values among the first E positions.

Brute force first. A candidate might start with BFS over arrangements (exponential) or simulate a sort. Neither is needed once the block argument is stated, but it is worth saying out loud why the answer is a count and not a simulation.

Two-pointer view (same answer). Put left at 0 and right at n-1. Move left right past evens and right left past odds. When left < right, nums[left] is odd and nums[right] is even, so swap them and count one. This is the in-place partition from Sort Array By Parity, and the number of swaps it performs equals k: left stops only on odds that lie before the boundary, and each such stop is matched by one swap. It is useful when the interviewer also wants the rearranged array.

Invariant for the two-pointer loop. Everything left of left is even, everything right of right is odd, and each swap removes one misplaced pair, never creating a new one.

Negative numbers. In Python -3 % 2 == 1, so x % 2 works. In languages where % keeps the sign, test x & 1 or x % 2 != 0 instead.

def min_swaps_evens_first(nums: list[int]) -> int:
    """Minimum swaps so every even precedes every odd. O(n) time, O(1) space."""
    evens = sum(1 for x in nums if x % 2 == 0)
    # Odds sitting in the slots that must hold evens; each needs one swap.
    return sum(1 for x in nums[:evens] if x % 2 == 1)


def partition_evens_first(nums: list[int]) -> int:
    """Rearrange nums in place (evens first) and return the swaps used.

    Uses the minimum number of swaps, so it agrees with min_swaps_evens_first.
    """
    left, right = 0, len(nums) - 1
    swaps = 0
    while left < right:
        if nums[left] % 2 == 0:
            left += 1
        elif nums[right] % 2 == 1:
            right -= 1
        else:
            nums[left], nums[right] = nums[right], nums[left]
            swaps += 1
            left += 1
            right -= 1
    return swaps


def min_swaps_odds_first(nums: list[int]) -> int:
    """Follow-up: odds must come first instead."""
    odds = sum(1 for x in nums if x % 2 == 1)
    return sum(1 for x in nums[:odds] if x % 2 == 0)


def min_swaps_either_order(nums: list[int]) -> int:
    """Follow-up: either block may come first; take the cheaper target."""
    return min(min_swaps_evens_first(nums), min_swaps_odds_first(nums))


def min_adjacent_swaps_evens_first(nums: list[int]) -> int:
    """Follow-up: only adjacent swaps allowed.

    Each even must jump over every odd to its left, and a stable move does
    exactly that, so the answer is the number of (odd, later even) pairs.
    """
    odds_seen = 0
    total = 0
    for x in nums:
        if x % 2 == 1:
            odds_seen += 1
        else:
            total += odds_seen
    return total


if __name__ == "__main__":
    import itertools
    import random

    assert min_swaps_evens_first([]) == 0
    assert min_swaps_evens_first([7]) == 0
    assert min_swaps_evens_first([2, 4, 1, 3]) == 0
    assert min_swaps_evens_first([1, 3, 2, 4]) == 2
    assert min_swaps_evens_first([5, 2, 8, 1, 6]) == 1
    assert min_swaps_evens_first([1, 2, 3, 4, 5, 6]) == 2
    assert min_swaps_evens_first([-3, -2, 0, 5]) == 1
    assert min_adjacent_swaps_evens_first([1, 3, 2, 4]) == 4
    assert min_swaps_either_order([1, 2, 2, 2]) == 0

    # Cross-check against BFS over arrangements on small inputs.
    def bfs_min_swaps(arr: list[int]) -> int:
        def ok(t: tuple[int, ...]) -> bool:
            p = [x % 2 for x in t]
            return p == sorted(p)
        start = tuple(arr)
        seen, frontier, depth = {start}, [start], 0
        while frontier:
            if any(ok(t) for t in frontier):
                return depth
            nxt = []
            for t in frontier:
                for i, j in itertools.combinations(range(len(t)), 2):
                    s = list(t)
                    s[i], s[j] = s[j], s[i]
                    u = tuple(s)
                    if u not in seen:
                        seen.add(u)
                        nxt.append(u)
            frontier, depth = nxt, depth + 1
        raise AssertionError("unreachable")

    for _ in range(300):
        arr = [random.randint(-9, 9) for _ in range(random.randint(0, 7))]
        expected = bfs_min_swaps(arr)
        assert min_swaps_evens_first(arr) == expected
        copy = arr[:]
        assert partition_evens_first(copy) == expected
        parities = [x % 2 for x in copy]
        assert parities == sorted(parities)
    print("all tests passed")

• min_swaps_evens_first: O(n) time (two passes), O(1) extra space if you index instead of slicing; the slice shown costs O(E).
• partition_evens_first: O(n) time, O(1) extra space, rearranges in place.
• Odds-first and either-order variants: O(n) time, O(1) space.
• Adjacent-swap variant: O(n) time, O(1) space.

• [] → 0 (empty array).
• [7] → 0 (single element).
• [2, 4, 1, 3] → 0 (already grouped).
• [1, 3, 5] → 0 (all odd; E = 0).
• [2, 6, 8] → 0 (all even).
• [1, 3, 2, 4] → 2 (both front slots hold odds).
• [5, 2, 8, 1, 6] → 1 (E = 3; front block [5, 2, 8] has one odd).
• [1, 2, 3, 4, 5, 6] → 2 (E = 3; front block [1, 2, 3] has two odds).
• [-3, -2, 0, 5] → 1 (negatives and zero; zero is even).
• Adjacent-only follow-up: [1, 3, 2, 4] → 4.
• Either-order follow-up: [1, 2, 2, 2] → 0 (odds-first already holds).

1. Return the arrangement too. Use the two-pointer partition. It performs exactly the minimum number of swaps and leaves the array grouped.
2. Either order is acceptable. Compute the evens-first count and the odds-first count (odd values in the first O slots, where O is the odd count) and return the smaller one.
3. Only adjacent swaps allowed. The answer becomes the number of inversions between parities: for each even, add the number of odds before it. One pass with a running odd count, O(n). This is the classic "group the 1s" count.
4. Keep relative order (stable). A stable partition cannot be done with arbitrary swaps at the minimum count. Either build two lists and concatenate (O(n) space), or if swaps must be adjacent, the adjacent-swap count above is already stable and optimal.
5. Generalize to k groups by a key (for example x % 3 in order 0, 1, 2). Count the slots each class should occupy, build the matrix cnt[a][b] = elements of class b sitting in class a's block. Resolve 2-cycles first (min(cnt[a][b], cnt[b][a]) swaps each), then each remaining 3-cycle costs 2 swaps. This is the Dutch national flag minimum-swap counting argument.

Mid-level (L4)

• Recognizes the link to Sort Array By Parity and writes a working two-pointer partition that counts swaps.
• Handles empty, all-even, and all-odd inputs without special cases breaking.
• States O(n) time and O(1) space.

Senior (L5)

• Reduces the problem to counting odds in the first E slots and proves it: misplaced odds equal misplaced evens, one swap fixes at most one pair.
• Notices the parity trap with negative numbers in languages whose % keeps the sign.
• Answers the either-order and adjacent-swap follow-ups quickly and explains why the answers differ.

Staff (L6+)

• Gives the lower-bound and matching upper-bound argument crisply before coding, and tests against a brute-force checker.
• Generalizes to k classes with the cycle-decomposition counting (2-cycles cost 1, 3-cycles cost 2) and discusses stability versus swap count.
• Discusses streaming or very large inputs: the count needs only two passes, or one pass if E is known.