You are given an integer array nums. Your task:

Return an array where all even numbers come first, followed by all odd numbers.

Important notes:

• The relative order does not need to be preserved
• You may return the result in-place or as a new array
• Only parity (even vs odd) matters, not sorting by value

Example:

Input:  [3,1,2,4]
Output: [2,4,3,1]

Another example:

Input: [0]
Output: [0]

---

Problem Understanding

Definition reminder:

• Even number: num % 2 == 0
• Odd number: num % 2 == 1 (or != 0 for negative values)

The goal is simply to partition the array so that:

evens appear before odds

Constraints:

• 1 ≤ nums.length ≤ 5000
• Values can be negative
• Order within evens or odds does not matter

This is a partitioning problem, not a sorting problem.

---

Logic Explained in Simple English

A straightforward way to think about the solution:

1. Create two buckets:
   • one for even numbers
   • one for odd numbers
2. Loop through the array:
   • If number is even, append to evens list
   • If number is odd, append to odds list
3. Combine evens followed by odds
4. Return result

Why this works:

• Every number is either even or odd
• Partitioning preserves all numbers
• No complex ordering rules

But there is an even more efficient way:

Two-pointer in-place approach:

1. Have a left pointer at start
2. Have a right pointer at end
3. While left < right:
   • If left is odd and right is even → swap them
   • If left is even → move left forward
   • If right is odd → move right backward

Why this works:

• Evens migrate to the left
• Odds migrate to the right
• No extra memory needed

---

Step-by-Step Approach (Two-Pointer In-Place)

1. Initialize left = 0
2. Initialize right = nums.length - 1
3. While left < right:
   • If nums[left] is even → left++
   • Else if nums[right] is odd → right–
   • Else swap nums[left] and nums[right]
4. Return nums

This ensures final array satisfies parity ordering.

---

Java Implementation

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            boolean leftIsEven = nums[left] % 2 == 0;
            boolean rightIsOdd = nums[right] % 2 != 0;
            
            if (leftIsEven) {
                left++;
            } else if (rightIsOdd) {
                right--;
            } else {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        
        return nums;
    }
}

---

Dry Run Example

Input:

[3,1,2,4]

Initial:

left = 0 (3 is odd)
right = 3 (4 is even)
swap → [4,1,2,3]
left = 1
right = 2

Next:

left = 1 (1 is odd)
right = 2 (2 is even)
swap → [4,2,1,3]
left = 2
right = 1

Stop because left >= right

Final Output:

[4,2,1,3]

All evens are first, odds later.

---

Time and Space Complexity

Time Complexity

O(n)

Every element is inspected at most once.

Space Complexity

O(1)

In-place, no extra arrays used.

---

Common Mistakes and How to Avoid Them

Mistake 1: Sorting the array

Sorting costs O(n log n) and is unnecessary.

Mistake 2: Using % 2 == 1 to detect odd numbers

Fails for negative numbers — better:

num % 2 != 0

Mistake 3: Preserving relative order

The problem explicitly says order does NOT matter.

Mistake 4: Returning only evens or only odds

Must return all numbers.

Mistake 5: Forgetting two-pointer stopping condition

Loop must end when:

left >= right