3587. Minimum Adjacent Swaps to Alternate Parity

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.

class Solution {
    int helper(vector<int>& A, int P) {
        deque<int> dq[2];
        for(int i = 0; i < A.size(); i++) dq[A[i]&1].push_back(i);
        int res = 0;
        for(int i = 0; i < A.size(); i++) {
            int p = i & 1 ? !P : P, np = !p;
            if(dq[p].size() == 0) return INT_MAX;
            if(dq[np].size() == 0) dq[p].pop_front();
            else {
                if(dq[p][0] < dq[np][0]) dq[p].pop_front();
                else {
                    res += dq[p][0] - i;
                    dq[p].pop_front();
                }
            }
        }
        return res;
    }
public:
    int minSwaps(vector<int>& nums) {
        int res = min(helper(nums,0), helper(nums,1));
        return res == INT_MAX ? -1 : res;
    }
};