Sort Array By Parity II - Video Solutions

Problem Overview: You receive an integer array where half the numbers are even and half are odd. Rearrange the array so that elements at even indices contain even numbers and elements at odd indices contain odd numbers.

Approach 1: Separate Arrays for Even and Odd Numbers (O(n) time, O(n) space)

This approach splits the array into two lists: one storing all even numbers and another storing all odd numbers. After collecting them, iterate through the original array and place values back such that even indices receive values from the even list and odd indices receive values from the odd list. The logic is straightforward and easy to reason about, making it a good starting point when you first see the problem. The trade‑off is extra memory because you store two additional arrays proportional to the input size. This method works well when clarity is more important than space efficiency and introduces the pattern of grouping values before reconstruction, a common technique in array manipulation problems.

Approach 2: Two Pointer Approach (O(n) time, O(1) space)

The optimal solution uses two pointers that jump across indices with the same parity. One pointer starts at index 0 and moves through even positions, while the other starts at index 1 and moves through odd positions. When the even pointer encounters an odd number and the odd pointer encounters an even number, swap them. Each pointer then advances by two positions. Because every element is examined at most once and swaps fix two incorrect placements simultaneously, the algorithm completes in linear time. This in-place technique avoids additional memory and demonstrates a classic two pointers strategy applied to index parity rather than array ends.

The key insight is that incorrect placements always occur in pairs: an odd number sitting in an even index must be matched with an even number sitting in an odd index. Swapping those two elements resolves both violations at once. The algorithm continues until both pointers reach the end of the array.

Although the problem can technically be solved by sorting or repeated searching for the correct parity element, those methods introduce unnecessary overhead compared to the direct pointer approach.

Recommended for interviews: The two pointer solution is what most interviewers expect. It runs in O(n) time and O(1) space while clearly demonstrating control over index traversal and in-place swapping. Mentioning the separate-arrays method first can show initial reasoning, but implementing the pointer-based approach signals stronger algorithmic thinking.