Sort Array By Parity

LeetCode 905: Sort Array By Parity Solution & Explanation

Problem Overview

TL;DR: Use two pointers starting at opposite ends of the array to swap elements in place, ensuring even numbers settle on the left and odd numbers on the right.

The Sort Array By Parity problem requires us to reorder an array of integers so that all even integers appear before all odd integers. The relative order of the even numbers or the odd numbers among themselves does not matter; any valid permutation that satisfies the "evens first, odds last" condition is acceptable. This is a fundamental array manipulation problem often used to test understanding of in-place algorithms.

This is a popular interview question that serves as an excellent introduction to partitioning algorithms, similar to those found in QuickSort.

Brute Force Approach for Sort Array By Parity

The most intuitive way to solve LeetCode 905 is to create a new array and populate it in two passes.

1. Create a new result array res.
2. Iterate through the input nums array. If a number is even, append it to res.
3. Iterate through the input nums array again. If a number is odd, append it to res.
4. Return res.

Pseudo-code

function sortArrayByParity(nums):
    result = []
    for x in nums:
        if x is even:
            result.append(x)
    for x in nums:
        if x is odd:
            result.append(x)
    return result

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the number of elements. We iterate through the array twice.
• Space Complexity: $O(N)$. We allocate a new array of size $N$ to store the result.

Why it fails (Context)

While this solution is correct and passes LeetCode's time constraints, it fails to meet the standard expectation for this class of problems in technical interviews. The problem tags and typical constraints imply an in-place solution is preferred. Allocating $O(N)$ extra space is inefficient when the operation can be performed by modifying the input array directly with $O(1)$ space.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Set a left pointer to index 0 and a right pointer to index n - 1.
2. Loop Condition: Continue execution as long as left < right.
3. Left Scan: Check the value at nums[left]. If nums[left] % 2 == 0 (even), this element is correctly placed. Increment left to process the next element.
4. Right Scan: Check the value at nums[right]. If nums[right] % 2 != 0 (odd), this element is correctly placed. Decrement right to process the previous element.
5. Swap: If the execution reaches this point inside the loop, it implies nums[left] is odd and nums[right] is even. Swap nums[left] and nums[right].
6. Termination: Once the pointers cross, all even numbers are to the left of the convergence point, and all odd numbers are to the right. Return the modified nums array.

Execution Flow

Consider the input nums = [3, 1, 2, 4].

1. Start: left = 0, right = 3.

   • nums[left] is 3 (Odd). It is out of place.
   • nums[right] is 4 (Even). It is out of place.
   • Action: Swap nums[0] and nums[3].
   • Array becomes [4, 1, 2, 3]. Increment left, decrement right.

2. Iteration 2: left = 1, right = 2.

   • nums[left] is 1 (Odd). It is out of place.
   • nums[right] is 2 (Even). It is out of place.
   • Action: Swap nums[1] and nums[2].
   • Array becomes [4, 2, 1, 3]. Increment left, decrement right.

3. Iteration 3: left = 2, right = 1.

   • Condition left < right is false.
   • Stop.

4. Result: [4, 2, 1, 3]. (Note: This is one valid output; evens 4, 2 are first, odds 1, 3 are last).

Proof of Correctness

The algorithm maintains the invariant that all elements in the range [0, left) are even and all elements in the range (right, n-1] are odd.

• In each step, we either increment left (validating an even number), decrement right (validating an odd number), or swap an invalid pair to make them valid.
• Since the distance between left and right decreases strictly with every valid operation or swap, the loop must terminate.
• Upon termination (left >= right), the union of the validated regions covers the entire array, ensuring the partition property holds.

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern used in Sort Array By Parity is highly reusable. Mastering this logic allows you to solve several other high-frequency interview problems:

• LeetCode 26: Remove Duplicates from Sorted Array - Uses a generic "read" and "write" pointer strategy to filter elements.
• LeetCode 27: Remove Element - Partitioning the array into "kept" and "removed" elements.
• LeetCode 75: Sort Colors - A more complex variation involving three partitions (0, 1, 2) instead of two (even, odd).
• LeetCode 80: Remove Duplicates from Sorted Array II - Similar to LC 26 but with relaxed constraints on duplicates.

In all these cases, the key is managing boundaries within the array to segregate data without external storage.

Reference Implementation

C++ Solution for LeetCode 905

1class Solution {
2public:
3    vector<int> sortArrayByParity(vector<int>& nums) {
4        int left = 0;
5        int right = nums.size() - 1;
6
7        while (left < right) {
8            if (nums[left] % 2 == 0) {
9                // Left element is already even (correct), move forward
10                left++;
11            } else if (nums[right] % 2 != 0) {
12                // Right element is already odd (correct), move backward
13                right--;
14            } else {
15                // Left is odd and Right is even: Swap them
16                std::swap(nums[left], nums[right]);
17                left++;
18                right--;
19            }
20        }
21        
22        return nums;
23    }
24};

Java Solution for LeetCode 905

1class Solution {
2    public int[] sortArrayByParity(int[] nums) {
3        int left = 0;
4        int right = nums.length - 1;
5
6        while (left < right) {
7            if (nums[left] % 2 == 0) {
8                // Left is even, correct position
9                left++;
10            } else if (nums[right] % 2 != 0) {
11                // Right is odd, correct position
12                right--;
13            } else {
14                // Left is odd, Right is even -> Swap
15                int temp = nums[left];
16                nums[left] = nums[right];
17                nums[right] = temp;
18                
19                left++;
20                right--;
21            }
22        }
23        
24        return nums;
25    }
26}

Python Solution for LeetCode 905

1class Solution:
2    def sortArrayByParity(self, nums: List[int]) -> List[int]:
3        left = 0
4        right = len(nums) - 1
5        
6        while left < right:
7            if nums[left] % 2 == 0:
8                # Left is even, correct position
9                left += 1
10            elif nums[right] % 2 != 0:
11                # Right is odd, correct position
12                right -= 1
13            else:
14                # Left is odd, Right is even -> Swap
15                nums[left], nums[right] = nums[right], nums[left]
16                left += 1
17                right -= 1
18                
19        return nums