The O(n) Club: Sort Array By Parity: When Evens Take the Lead (and Odds Wait in Line)

The O(n) Club: Sort Array By Parity — When Evens Take the Lead (and Odds Wait in Line)

⚡ TL;DR

You want all the even numbers at the start and all the odds at the end, and you don’t care about the order inside each group? Great, neither does this algorithm. Here’s one unreasonably honest (but classic) brute-force answer in Java:

// Brute force
int[] sortArrayByParity(int[] nums) {
    List
<integer> evens = new ArrayList<>();
    List
<integer> odds = new ArrayList<>();
    for (int n : nums) if (n % 2 == 0) evens.add(n); else odds.add(n);
    evens.addAll(odds);
    return evens.stream().mapToInt(Integer::intValue).toArray();
}</integer></integer>

🧠 How Devs Usually Mess This Up

Raise your hand if you’ve:

• Assumed output order matters (news flash: it doesn’t—this isn’t a wedding seating chart)
• Used more for-loops than necessary, hoping to brute force your way to elegance
• Brought a new array to an “in-place” interview fight (instant regret!)
• Confused this with “Parity II” and tried to put evens/odds at even/odd indices (wrong party, pal)

🔍 What’s Actually Going On

Imagine your array as a club line where only even-numbered people get to skip to the front; odds stumble in behind them, grumbling. Your job is to let the bouncer (your two pointers) swap the misfits until all the VIPs (evens) are up front. We don’t care if the even crowd keeps their original order as long as they’re together—not exactly “sorted”, just… well… sorted by group.

🛠️ PseudoCode

• Start with two pointers: One at the left (left = 0), one at the right (right = nums.length - 1).
• While left < right:
  • If nums[left] is even, great—move left pointer up.
  • If nums[right] is odd, great—move right pointer down.
  • If left is odd & right is even: swap them. Move both pointers in.
• Repeat until pointers collide and you smell O(n) efficiency.

💻 The Code

// Two-pointer, in-place (use this to look smart)
public int[] sortArrayByParity(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        while (left < right && nums[left] % 2 == 0) left++;
        while (left < right && nums[right] % 2 == 1) right--;
        if (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    return nums;
}

Or, for the safety-net crowd:

// Extra array, fewer headaches, but not in-place
public int[] sortArrayByParity(int[] nums) {
    int[] out = new int[nums.length];
    int start = 0, end = nums.length - 1;
    for (int n : nums) {
        if (n % 2 == 0) out[start++] = n;
        else out[end--] = n;
    }
    return out;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All evens or all odds? Nothing happens. Don’t overthink it.
• Zero is even. Seriously. Every. Time. (If you ask your interviewer, you owe coffee.)
• Integer overflow? Not even close—you’re just comparing %2.
• Time: O(n). You loop once. You can finish before your coffee gets cold.
• Space: O(1) if in-place; O(n) if you bring a friend (array).

🧠 Interviewer Brain-Tattoo

“Sorting by parity: the rare interview question where brute force is almost as good as genius. If a swap feels right, it probably is.”