Sort Array By Parity

Sort Array By Parity

What is this problem about?

"Sort Array By Parity" is a fundamental array manipulation problem that is often used as an introductory challenge in technical interviews. You are given an array of non-negative integers, and your task is to rearrange the elements such that all the even integers appear at the beginning of the array, followed by all the odd integers.

The relative order of the even numbers among themselves doesn't matter, and the same applies to the odd numbers. The goal is simply to partition the array based on parity (divisibility by 2) in the most efficient way possible, ideally in-place to save space.

Why is this asked in interviews?

Companies like Apple, Microsoft, and Meta ask this interview question to assess a candidate's basic understanding of array traversal and in-place modification. It’s a classic test of whether you can implement a simple partitioning logic without using extra space ($O(1)$ space complexity). It also serves as a precursor to more complex partitioning algorithms like the one used in Quick Sort.

Algorithmic pattern used

The primary algorithmic pattern is the Two Pointers technique. You maintain two pointers: one starting at the beginning of the array (left) and one at the end (right).

• If the element at left is even, move left forward.
• If the element at right is odd, move right backward.
• If left is pointing to an odd number and right is pointing to an even number, swap them and then move both pointers. This continues until the pointers meet, ensuring all evens are on the left and odds are on the right in $O(N)$ time.

Example explanation

Input: [3, 1, 2, 4]

1. left = 0 (val 3), right = 3 (val 4).
2. 3 is odd and 4 is even. Swap them: [4, 1, 2, 3].
3. left = 1 (val 1), right = 2 (val 2).
4. 1 is odd and 2 is even. Swap them: [4, 2, 1, 3].
5. left and right now point to the same area or cross. Result: [4, 2, 1, 3].

Common mistakes candidates make

One common mistake is using an auxiliary array, which increases the space complexity to $O(N)$. While this works, it’s not the optimal solution interviewers are looking for. Another mistake is incorrect boundary conditions in the two-pointer loop, leading to infinite loops or out-of-bounds errors. Some candidates also overcomplicate the logic by trying to maintain the original relative order (stable sort), which is not required by this specific sort array by parity coding problem.

Interview preparation tip

When you see a problem that asks to "group" or "partition" elements based on a property, your first thought should be Two Pointers. Practice this pattern on similar problems like "Move Zeroes" or "Remove Element." Being able to explain the trade-offs between an in-place $O(1)$ space solution and a simpler $O(N)$ space solution demonstrates strong engineering judgment.