Pseudo-code

text
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.

Core Insight for Sort Array By Parity

The core insight for the optimal LeetCode 905 Solution is to view the array as a container that needs to be partitioned. We can maintain an invariant where the left side of the array only contains even numbers and the right side only contains odd numbers.

We define two pointers:

1. left: Starts at the beginning (0) and looks for odd numbers that are out of place.
2. right: Starts at the end (n-1) and looks for even numbers that are out of place.

The logic proceeds by checking the elements at these pointers:

• If nums[left] is even, it is already in the correct position relative to the partition. We advance left.
• If nums[right] is odd, it is already in the correct position. We decrement right.
• If nums[left] is odd AND nums[right] is even, both elements are in the wrong partition. We swap them. After the swap, the element at left becomes even (correct) and the element at right becomes odd (correct).

Visual Description: Imagine the array indices as a horizontal range. The left pointer defines the boundary of the "processed even" region growing from the start. The right pointer defines the boundary of the "processed odd" region growing from the end. The area between left and right is the "unprocessed" zone. The algorithm shrinks this unprocessed zone until it vanishes when left meets right.

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.

Reference Implementation

C++ Solution for LeetCode 905

cpp
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            if (nums[left] % 2 == 0) {
                // Left element is already even (correct), move forward
                left++;
            } else if (nums[right] % 2 != 0) {
                // Right element is already odd (correct), move backward
                right--;
            } else {
                // Left is odd and Right is even: Swap them
                std::swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }
        
        return nums;
    }
};

Java Solution for LeetCode 905

java
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            if (nums[left] % 2 == 0) {
                // Left is even, correct position
                left++;
            } else if (nums[right] % 2 != 0) {
                // Right is odd, correct position
                right--;
            } else {
                // Left is odd, Right is even -> Swap
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
        
        return nums;
    }
}

Python Solution for LeetCode 905

python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1
        
        while left < right:
            if nums[left] % 2 == 0:
                # Left is even, correct position
                left += 1
            elif nums[right] % 2 != 0:
                # Right is odd, correct position
                right -= 1
            else:
                # Left is odd, Right is even -> Swap
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
                
        return nums