LeetCode: Sort Array By Parity II

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Iterate the array twice

One obvious solution is iterating the array, put odd and even values into suitable positions. Because we don’t care the order of elements.

Time complexity O(N), space complexity is O(N).

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n = A.size();
        vector<int> ans(n);

        int i = 0;
        for (int x: A) {
            if (x % 2 == 0) {
                ans[i] = x;
                i += 2;
            }
        }
        i = 1;
        for (int x: A) {
            if (x % 2 == 1) {
                ans[i] = x;
                i += 2;
            }
        }
        return ans;
    }
};

Swap even and odd positions

Another solution is try to find a pair of indexes which is not follow the required property, then swap them.

We continue to do this until we go through the whole array.

Time complexity is O(N).

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

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Defuse the Bomb LeetCode: Groups of Special-Equi... →