Sort Array By Parity II

Sort Array By Parity II

What is this problem about?

"Sort Array By Parity II" is a variation of the original parity problem with a stricter requirement. You are given an array of integers where half of the integers are odd and half are even. Your task is to sort the array so that whenever nums[i] is even, i is also even, and whenever nums[i] is odd, i is also odd.

Essentially, you are alternating even and odd numbers such that they "match" their index parity. This adds a layer of complexity because you are no longer just grouping them at two ends; you are placing them in specific, alternating slots.

Why is this asked in interviews?

This coding problem is used by companies like Microsoft and Google to see if a candidate can adapt a known pattern (Two Pointers) to a more constrained scenario. It tests your ability to manage multiple pointers simultaneously and your understanding of array indexing. It’s also a good exercise in writing clean loop logic that avoids redundant checks.

Algorithmic pattern used

The most efficient pattern is a modified Two Pointers approach. You maintain two "write" pointers: even_ptr (starting at 0) and odd_ptr (starting at 1).

• Iterate through the array. Whenever you find an even number at an odd index (or vice versa), you need to fix it.
• A better way: Use even_ptr to find an even index that has an odd number, and odd_ptr to find an odd index that has an even number.
• Once both are found, swap the elements and increment both pointers by 2. This achieves the result in a single pass ($O(N)$ time) and in-place ($O(1)$ space).

Example explanation

Input: [4, 2, 5, 7]

• Index 0: 4 (even, correct).
• Index 1: 2 (even, should be odd). odd_ptr stops here.
• Find an even index with an odd number: Index 2 has 5 (odd, should be even). even_ptr stops here.
• Swap nums[1] and nums[2]: [4, 5, 2, 7].
• Index 2: 2 (even, correct).
• Index 3: 7 (odd, correct). Result: [4, 5, 2, 7].

Common mistakes candidates make

A frequent error is trying to sort the entire array first and then re-arranging it, which is inefficient. Another mistake is using nested loops that result in $O(N^2)$ time complexity. Candidates also often forget to increment their pointers by 2 (to stay on even/odd indices), leading to them checking the same indices repeatedly or incorrectly.

Interview preparation tip

For the "Sort Array By Parity II interview question," focus on the logic of "finding the next mismatch." This mindset is helpful for many array-matching problems. Practice writing the while-loops that advance the pointers to the next invalid state. This ensures you don't swap elements that are already in their correct positions.