Sort Array By Parity - Video Solutions

Problem Overview: You receive an integer array and must reorder it so that all even numbers appear before all odd numbers. The relative order does not matter. Any valid arrangement where every even value comes before every odd value is accepted.

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

This approach treats the array like a partitioning problem. Use two pointers: one starting from the left and one from the right. The left pointer searches for an odd number that is misplaced, while the right pointer searches for an even number that should move forward. When both conditions are met, swap the elements and move both pointers inward. Each element is inspected at most once, which keeps the runtime linear. This in-place strategy is memory efficient and mirrors the partition logic used in quicksort-style problems. It is a common pattern when working with two pointers on an array.

The key insight is that you do not need full sorting. The task only requires grouping elements by parity. By continuously correcting misplaced elements from both ends, the array gradually forms two partitions: evens on the left and odds on the right. Because swaps occur directly inside the original array, no extra memory is required.

Approach 2: Separate and Concatenate (O(n) time, O(n) space)

This method builds two temporary lists while iterating through the array once. During the iteration, check each element with num % 2. Append even numbers to one list and odd numbers to another. After the pass completes, concatenate the even list with the odd list to produce the final result. The logic is straightforward and easy to implement, making it a good baseline solution when clarity matters more than memory usage.

The tradeoff is extra space. Since two auxiliary lists are created, the space complexity grows linearly with the input size. However, the runtime remains O(n) because each element is processed once. Conceptually, this approach resembles a simplified grouping step often used before sorting or partitioning operations.

Recommended for interviews: The two-pointer technique is the solution most interviewers expect. It demonstrates that you recognize this as a partition problem and can solve it in-place with O(n) time and O(1) space. The separate-and-concatenate approach still shows correct reasoning and linear processing, but the additional memory makes it less optimal.