Transform Array by Parity - Solution & Explanation

Problem Overview: You are given an integer array and need to transform it so that elements are grouped by parity. All even numbers should appear before odd numbers in the final array. The relative order usually does not matter, so the goal is simply to separate values based on whether num % 2 == 0.

Approach 1: Sorting by Parity (O(n log n) time, O(1) space)

A straightforward way is to sort the array using a custom comparator that prioritizes even numbers over odd numbers. Most languages allow sorting with a key such as num % 2, which naturally places even values first. This works because even numbers evaluate to 0 and odd numbers to 1. The approach relies on standard sorting algorithms, which typically run in O(n log n) time and use constant or logarithmic extra space depending on implementation. It is simple but slower than necessary for this problem.

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

You can treat the array like a partition problem. Maintain two pointers: one from the start and one from the end. Move the left pointer forward while it points to even numbers, and move the right pointer backward while it points to odd numbers. When an odd number appears on the left and an even number on the right, swap them. This approach processes each element at most once, making it linear time. The idea is similar to partitioning used in quicksort and works well for problems involving arrays and in-place rearrangement.

Approach 3: Counting Evens and Odds (O(n) time, O(1) extra space)

The counting strategy is the simplest when you only need the final parity grouping. First iterate through the array and count how many elements are even. Then overwrite the array: fill the first evenCount positions with even numbers and the remaining positions with odd numbers while scanning the original data. This approach relies on a simple counting technique and sequential iteration. Because it performs two linear passes and only stores a few counters, it runs in O(n) time with constant space.

Recommended for interviews: The two-pointer or counting approach is what interviewers expect. Sorting shows you understand the requirement but wastes time complexity. Demonstrating an O(n) partition or counting solution shows stronger control over array traversal and in-place transformations.