Problem Description

You have an array nums containing distinct integers. Your goal is to rearrange this array so that adjacent elements have alternating parity (one even, one odd).

You can only swap two adjacent elements at a time. For example, if you have [1, 2, 3], you can swap positions 0 and 1 to get [2, 1, 3], or swap positions 1 and 2 to get [1, 3, 2].

A valid arrangement means that for every pair of neighboring elements in the array, one must be even and the other must be odd. For instance:

• [1, 2, 3, 4] is valid (odd-even-odd-even pattern)
• [2, 1, 4, 3] is valid (even-odd-even-odd pattern)
• [1, 3, 2, 4] is NOT valid (1 and 3 are both odd and adjacent)

Your task is to find the minimum number of adjacent swaps needed to transform the given array into any valid arrangement. If it's impossible to create a valid arrangement (for example, if you have 5 odd numbers and only 1 even number), return -1.

The key insight is that for a valid alternating pattern to exist, the counts of odd and even numbers can differ by at most 1. If you have n elements total:

• If n is even, you need exactly n/2 odd numbers and n/2 even numbers
• If n is odd, you need either (n+1)/2 odd and (n-1)/2 even, or (n-1)/2 odd and (n+1)/2 even

The solution tracks the positions of odd and even numbers separately, then calculates how many swaps are needed to move them to their target positions in a valid alternating arrangement.

Intuition

Think about what a valid arrangement looks like - it must follow either an even-odd-even-odd pattern or an odd-even-odd-even pattern. This means elements need to be in specific positions based on their parity.

First, let's consider when a valid arrangement is even possible. If we have n total elements and they need to alternate, then:

• For even n: we need exactly n/2 odd and n/2 even numbers
• For odd n: we need one extra of either odd or even numbers

If the difference between odd and even counts is more than 1, it's impossible to create an alternating pattern.

Now, how do we count the minimum swaps? The key insight is that we only care about getting each number to a valid position, not the specific order within odd or even groups.

Consider this: if we decide to start with an even number, then all even numbers should be at positions 0, 2, 4, ... and all odd numbers should be at positions 1, 3, 5, ... We can track where each even number currently is and where it needs to go.

For example, if we have [1, 2, 3, 4] and want the pattern to be even-odd-even-odd:

• Even numbers (2, 4) need to be at positions 0 and 2
• Currently, 2 is at position 1 and 4 is at position 3
• We need to move 2 from position 1 to position 0 (distance = 1)
• We need to move 4 from position 3 to position 2 (distance = 1)
• Total moves = 2

The brilliant part is that counting the total distance each element needs to move gives us the minimum swaps! This works because when we swap adjacent elements, we're essentially "bubbling" elements to their target positions, and the sum of distances equals the number of swaps needed.

When odd and even counts are equal, we have two possible patterns to try (starting with odd or starting with even), and we take the minimum. When counts differ by 1, only one pattern is possible - the more frequent parity must occupy the extra position.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a systematic approach to calculate the minimum swaps:

1. Separate elements by parity: We create a 2D list pos where:

• pos[0] stores all indices of even numbers
• pos[1] stores all indices of odd numbers

This is done by iterating through nums and using x & 1 to determine parity (0 for even, 1 for odd).

2. Check validity: Calculate the difference between counts: abs(len(pos[0]) - len(pos[1])). If this difference is greater than 1, return -1 immediately as no valid arrangement exists.

3. Define the calculation function: The calc(k) function computes swaps needed when starting with parity k:

• If k = 0, we want even numbers at positions 0, 2, 4, ...
• If k = 1, we want odd numbers at positions 0, 2, 4, ...

The function uses: sum(abs(i - j) for i, j in zip(range(0, len(nums), 2), pos[k]))

This calculates:

• range(0, len(nums), 2) generates target positions: 0, 2, 4, ...
• pos[k] contains current positions of numbers with parity k
• For each pair (i, j), abs(i - j) is the distance that element at position j needs to move to reach position i
• The sum gives total moves needed

4. Determine which patterns to try:

• If len(pos[0]) > len(pos[1]): More even numbers, so evens must occupy positions 0, 2, 4, ... Return calc(0)
• If len(pos[0]) < len(pos[1]): More odd numbers, so odds must occupy positions 0, 2, 4, ... Return calc(1)
• If len(pos[0]) == len(pos[1]): Equal counts, try both patterns and return min(calc(0), calc(1))

Example walkthrough: For nums = [3, 1, 2, 4]:

• pos[0] = [2, 3] (positions of even numbers 2, 4)
• pos[1] = [0, 1] (positions of odd numbers 3, 1)
• Equal counts, so try both patterns
• Pattern 1 (even first): Target positions for evens are 0, 2. Cost = |0-2| + |2-3| = 3
• Pattern 2 (odd first): Target positions for odds are 0, 2. Cost = |0-0| + |2-1| = 1
• Return minimum = 1

The algorithm efficiently computes the answer in O(n) time by leveraging the fact that the sum of distances equals the minimum number of adjacent swaps needed.

Example Walkthrough

Let's walk through the solution with nums = [3, 5, 2, 6].

Step 1: Separate by parity

• Even numbers: 2 (at index 2), 6 (at index 3)
• Odd numbers: 3 (at index 0), 5 (at index 1)
• pos[0] = [2, 3] (positions of evens)
• pos[1] = [0, 1] (positions of odds)

Step 2: Check validity

• Even count: 2, Odd count: 2
• Difference: |2 - 2| = 0 ≤ 1 ✓ Valid

Step 3: Try both patterns

Pattern 1: Even-Odd-Even-Odd

• Target positions for evens: 0, 2
• Current positions of evens: 2, 3
• Calculate moves:
  • First even (at 2) needs to reach position 0: |0 - 2| = 2 moves
  • Second even (at 3) needs to reach position 2: |2 - 3| = 1 move
• Total: 2 + 1 = 3 swaps

Pattern 2: Odd-Even-Odd-Even

• Target positions for odds: 0, 2
• Current positions of odds: 0, 1
• Calculate moves:
  • First odd (at 0) needs to reach position 0: |0 - 0| = 0 moves
  • Second odd (at 1) needs to reach position 2: |2 - 1| = 1 move
• Total: 0 + 1 = 1 swap

Step 4: Return minimum

• min(3, 1) = 1

The actual swap sequence would be: swap positions 1 and 2 to get [3, 2, 5, 6], which follows the odd-even-odd-even pattern.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs the following operations:

• One pass through the array to build the pos lists, which takes O(n) time
• The calc function computes the sum of absolute differences between corresponding positions. In the worst case, it processes approximately n/2 elements (when the array is evenly split between 0s and 1s), performing O(1) work for each element, resulting in O(n) time
• The algorithm calls calc at most twice (when counts are equal), each taking O(n) time
• All other operations (length comparisons, min calculation) take O(1) time

Therefore, the overall time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses:

• Two lists in pos to store the positions of 0s and 1s. Combined, these lists store exactly n positions (every element's index is stored exactly once), requiring O(n) space
• The range object in the calc function generates values on-the-fly and doesn't consume additional space proportional to n
• All other variables use O(1) space

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Distance Sum as Number of Swaps

The Pitfall: A common misconception is thinking that the sum of distances sum(abs(i - j)) might overcount or undercount the actual number of adjacent swaps needed. Developers often try to divide this sum by 2 or apply other transformations, thinking elements are being moved twice.

Why This Happens: When visualizing the swapping process, it seems like moving one element might affect others, leading to the belief that simple distance summation is incorrect.

The Solution: The sum of distances is exactly equal to the minimum number of adjacent swaps. Here's why:

• When we calculate abs(target_pos - current_pos) for each element, we're counting how many positions it needs to move
• Adjacent swaps can be thought of as "bubble sort" movements
• Each unit of distance requires exactly one adjacent swap
• Elements moving in opposite directions don't interfere - they pass through each other via swaps

Correct Understanding Example:

# If element at index 3 needs to move to index 0:
# [a, b, c, X] -> [a, b, X, c] -> [a, X, b, c] -> [X, a, b, c]
# Distance = 3, Swaps needed = 3

2. Incorrectly Handling the Equal Count Case

The Pitfall: When even and odd counts are equal, developers sometimes arbitrarily choose one pattern without checking both possibilities.

Incorrect Implementation:

if even_count == odd_count:
    return calculate_swaps(0)  # Wrong! Only checks one pattern

The Solution: Always check both patterns when counts are equal and return the minimum:

if even_count == odd_count:
    return min(calculate_swaps(0), calculate_swaps(1))

This is crucial because depending on the initial arrangement, one pattern might require significantly fewer swaps than the other.

3. Off-by-One Errors in Parity Checking

The Pitfall: Using incorrect logic to determine which parity should start at position 0 when counts are unequal.

Common Mistake:

# Incorrect logic - reversed conditions
if odd_count > even_count:
    return calculate_swaps(0)  # Wrong! Should be calculate_swaps(1)

The Solution: Remember the rule: whichever parity has more elements MUST occupy positions 0, 2, 4, ... (the positions generated by range(0, len(nums), 2)).

• If more odds exist, odds go to positions 0, 2, 4, ... → calculate_swaps(1)
• If more evens exist, evens go to positions 0, 2, 4, ... → calculate_swaps(0)

4. Not Recognizing Impossible Cases Early

The Pitfall: Attempting to calculate swaps even when the difference in counts makes alternating arrangement impossible.

The Solution: Always validate feasibility first:

if abs(even_count - odd_count) > 1:
    return -1

This check should come before any swap calculations to avoid unnecessary computation and potential errors.