Parity Sorting the Array by Index

Similar to Parity Sorting, the Index Parity Sorting can be applied to an array of integers that have equal number of even numbers and odd numbers. You are to re-arrange the integers so that A[i] is even when i is even and A[j] is odd when j is odd.

It is obvious that you can index parity sort the array more than one way – you may return any of them that satisfy the requirements.

Even and Odd Index Pointers

We can define two index pointers starting at 0 and 1 respectively. Iterating the array and place the numbers at the corresponding index – then increment the index by two.

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        vector<int> r(A.size());
        int even = 0, odd = 1;
        for (int i = 0; i < A.size(); ++ i) {
            if (A[i] % 2 == 0) {
                r[even] = A[i];
                even += 2;
            } else {
                r[odd] = A[i];
                odd += 2;
            }
        }
        return r;
    }
};

The complexity is O(N) and the space complexity is O(N) – the extra array to return the result. We may also transform above idea into a more concise implementation using an indices array.

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int indices[2] = { -2, -1 };
        vector<int> ret(A.size());
        for (int i = 0; i < A.size(); ++ i) {
            ret[indices[A[i] % 2] += 2] = A[i];
        }
        return ret;
    }
};

In-Place

If we do it in-place without allocating a new array, the complexity is still O(N^2) but the space complexity is O(1).

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int indexes[2] = { -2, -1 };
        for (int i = 0; i < A.size(); ++i) {
            while (A[i] % 2 != i % 2) {
                int idx = (indexes[A[i] % 2] += 2);
                swap(A[i], A[idx]);
            }
        }
        return A;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —