Problem Description

You are given an array nums of distinct integers.

In one operation, you can swap any two adjacent elements in the array.

An arrangement of the array is considered valid if the parity of adjacent elements alternates, meaning every pair of neighboring elements consists of one even and one odd number.

Return the minimum number of adjacent swaps required to transform nums into any valid arrangement.

If it is impossible to rearrange nums such that no two adjacent elements have the same parity, return -1.

Intuition

To create a valid arrangement where even and odd numbers alternate, we first notice that the counts of even and odd numbers must be nearly balanced—either equal or differing by only one. Otherwise, alternating them throughout the array is impossible.

If the balance is okay, we want to form new arrangements where the pattern is either even-odd-even-odd or odd-even-odd-even, depending on which parity starts first. By tracking the positions of even and odd numbers in the original array, we can figure out, for each valid pattern, how many moves are needed for each even and odd number to reach their target spots. Each swap moves a number one position, so the total swaps for a pattern is the sum of the distances each number must travel to get to their alternating place.

By checking both possible starting patterns (starting with even or with odd), and calculating the minimum moves for each, we determine the smallest number of adjacent swaps needed.

Solution Approach

The solution uses case analysis and a greedy approach:

1. Counting Odd and Even Numbers:

   • First, count how many even and odd numbers are in the input array nums by iterating through it.
   • Store the indices of even numbers in pos[0] and indices of odd numbers in pos[1].

2. Feasibility Check:

   • If the counts of even and odd numbers differ by more than 1 (abs(len(pos[0]) - len(pos[1])) > 1), a valid alternating arrangement is impossible. In such cases, return -1.

3. Calculating Minimum Swaps:

   • Define a helper function calc(k), where k is the parity to start with (0 for even, 1 for odd).
   • The function calc(k) computes the sum of the absolute differences between the current indices of elements of parity k and their target positions in the ideal alternating arrangement (range(0, len(nums), 2)).
   • For example, if the arrangement starts with even (k=0), the even numbers should be at positions 0, 2, 4, ..., and the function sums up how far each actual even number is from those positions.

4. Evaluating Both Arrangements:

   • If the counts are equal, try both starting with even and starting with odd. Return the minimum swaps of the two patterns: min(calc(0), calc(1)).
   • If there are more even numbers, only the arrangement starting with even is valid, so return calc(0).
   • Similarly, if there are more odd numbers, only the arrangement starting with odd is valid, so return calc(1).

Algorithm Summary in Steps:

• Collect indices of even and odd elements.
• Check if counts differ by at most 1.
• For each possible valid starting parity, calculate swaps needed to move all elements of that parity to their correct positions in the alternating pattern.
• Return the minimum swaps found.

All calculations use simple greedy moves and index tracking, ensuring an efficient solution.

Example Walkthrough

Consider nums = [3, 2, 4, 1].

Step 1: Collect Indices by Parity

• Even indices: positions where values are even → nums[1]=2, nums[2]=4 → pos[0] = [1, 2]
• Odd indices: positions where values are odd → nums[0]=3, nums[3]=1 → pos[1] = [0, 3]

So, even_count = 2, odd_count = 2.

Step 2: Feasibility Check

|even_count - odd_count| = |2 - 2| = 0 ≤ 1 We can proceed.

Step 3: Calculate Minimum Swaps

We need to try both starting parities.

(A) Start With Even (k=0): Even, Odd, Even, Odd

• Target even positions: 0 and 2

• Actual even indices: [1, 2]

• Swaps needed:

  • Move from 1 to 0 → |1-0| = 1
  • Move from 2 to 2 → |2-2| = 0 Total for evens: 1

• Target odd positions: 1 and 3

• Actual odd indices: [0, 3]

• Swaps needed:

  • Move from 0 to 1 → |0-1| = 1
  • Move from 3 to 3 → |3-3| = 0 Total for odds: 1

• Total swaps: 1 (even) + 1 (odd) = 2

(B) Start With Odd (k=1): Odd, Even, Odd, Even

• Target odd positions: 0 and 2

• Actual odd indices: [0, 3]

• Swaps needed:

  • 0 → 0 = 0
  • 3 → 2 = 1 Total: 1

• Target even positions: 1 and 3

• Actual even indices: [1, 2]

• Swaps needed:

  • 1 → 1 = 0
  • 2 → 3 = 1 Total: 1

• Total swaps: 1 (odd) + 1 (even) = 2

Step 4: Final Answer

Take the minimum from both patterns: min(2, 2) = 2

Summary: For nums = [3, 2, 4, 1], arranging as [2, 3, 4, 1] or [3, 2, 1, 4] takes a minimum of 2 adjacent swaps to achieve alternating parity, following the outlined approach.

Solution Implementation

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the array nums. This is because the code iterates through nums once to populate the pos lists and, for at most two calls, computes sum(abs(i - j) ...) over all positions, which in total takes linear time.

• Space Complexity: O(n), since the auxiliary arrays pos[0] and pos[1] together store the indices of all elements in nums, consuming linear extra space.