# Sort Array By Parity
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-array-by-parity)
Canonical: https://scaleengineer.com/dsa/problems/sort-array-by-parity
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [DXC Technology](https://scaleengineer.com/companies/dxc-technology)
---
## Problem
Given an integer array `nums`, move all the even integers at the beginning of the array followed by all the odd integers.

Return _**any array** that satisfies this condition_.

**Example 1:**

**Input:** nums = [3,1,2,4]
**Output:** [2,4,3,1]
**Explanation:** The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

**Example 2:**

**Input:** nums = [0]
**Output:** [0]

**Constraints:**

* `1 <= nums.length <= 5000`
* `0 <= nums[i] <= 5000`

# Approaches
## Sort with Custom Comparator
This approach treats the problem as a custom sorting problem. We can use a standard sorting algorithm, but with a custom comparison logic. The logic is simple: even numbers are considered "smaller" than odd numbers. This ensures that after sorting, all even numbers will appear before all odd numbers.
**Time:** O(N log N). The dominant operation is the sort, which typically has this time complexity. The conversions to and from `Integer[]` take O(N) time. · **Space:** O(N). We need an auxiliary array of `Integer` objects to use the custom comparator with `Arrays.sort`.
**Pros:** Conceptually simple and relies on a well-known library function.; The code is concise and easy to write.
**Cons:** Not the most efficient time complexity for this specific problem.; Requires extra space for the boxed `Integer` array, which also adds overhead.
### Explanation
The core idea is to define a custom comparator that guides the sorting process. The comparator for two numbers, `a` and `b`, will return a negative value if `a` should come before `b`, a positive value if `b` should come before `a`, and zero if their order doesn't matter relative to the parity rule. The comparison can be based on the result of the modulo-2 operation (`x % 2`). An even number gives `0`, and an odd number gives `1`. So, we can simply sort based on `a % 2` vs `b % 2`. In Java, `Arrays.sort()` on primitive arrays doesn't accept a custom comparator. A common way to handle this is to convert the `int[]` to an `Integer[]`, sort the `Integer[]`, and then copy it back.

```java
import java.util.Arrays;

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        Integer[] numsInteger = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsInteger[i] = nums[i];
        }

        Arrays.sort(numsInteger, (a, b) -> Integer.compare(a % 2, b % 2));

        for (int i = 0; i < nums.length; i++) {
            nums[i] = numsInteger[i];
        }
        return nums;
    }
}
```
### Algorithm
- Create a new `Integer` array of the same size as the input `nums` array.
- Copy the elements from `nums` to the new `Integer` array.
- Use `Arrays.sort()` with a custom lambda comparator: `(a, b) -> Integer.compare(a % 2, b % 2)`. This sorts the array by placing even numbers (where `x % 2` is 0) before odd numbers (where `x % 2` is 1).
- Copy the sorted elements from the `Integer` array back to the original `nums` array.
- Return the modified `nums` array.

## Two-Pass with Extra Array
This is a straightforward approach that uses an auxiliary array to build the result. We iterate through the input array twice. In the first pass, we collect all the even numbers and place them at the beginning of the new array. In the second pass, we collect all the odd numbers and place them after the even numbers.
**Time:** O(N). We iterate through the input array `nums` two times, which is 2 * N operations, resulting in a linear time complexity. · **Space:** O(N). We allocate an additional array `result` of the same size as the input array.
**Pros:** Easy to understand and implement.; More time-efficient than the sorting approach with a linear time complexity.
**Cons:** Requires extra space, which might be a constraint in some scenarios.; It doesn't modify the array in-place.
### Explanation
We first allocate a new array, `result`, of the same size as the input `nums`. We maintain an index, let's call it `writeIndex`, to keep track of the next available position in the `result` array.

**First Pass (for evens):** We iterate through the original `nums` array. Whenever we encounter an even number, we place it at `result[writeIndex]` and increment `writeIndex`. After this pass, the first part of `result` is filled with all the even numbers from `nums`.

**Second Pass (for odds):** We iterate through `nums` again. This time, whenever we find an odd number, we place it at `result[writeIndex]` and increment `writeIndex`. Finally, the `result` array will contain all even numbers followed by all odd numbers.

```java
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int[] result = new int[nums.length];
        int index = 0;
        
        // First pass: place all even numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                result[index++] = num;
            }
        }
        
        // Second pass: place all odd numbers
        for (int num : nums) {
            if (num % 2 != 0) {
                result[index++] = num;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize a new integer array `result` of size `nums.length`.
- Initialize a pointer `index = 0`.
- Iterate through each `num` in the input array `nums`. If `num` is even (`num % 2 == 0`), assign `result[index] = num` and increment `index`.
- Iterate through each `num` in the input array `nums` again. If `num` is odd (`num % 2 != 0`), assign `result[index] = num` and increment `index`.
- Return the `result` array.

## In-place Two-Pointer Approach
This is the most optimal approach. It modifies the array in-place, avoiding the need for extra space. It uses two pointers to partition the array into even and odd sections. One common implementation is similar to the partitioning step of the Quick Sort algorithm.
**Time:** O(N). We iterate through the array only once. Each element is visited and processed at most a constant number of times. · **Space:** O(1). The sorting is done in-place, so we only use a constant amount of extra space for pointers and temporary variables for swapping.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) as it's an in-place algorithm.
**Cons:** The relative order of elements with the same parity is not preserved (though the problem statement allows this).
### Explanation
We use two pointers. One pointer, `insertPos`, tracks the boundary where the next even number should be placed. The other pointer, `current`, iterates through the entire array to examine each element. The invariant we maintain is that all elements before `insertPos` are even. When the `current` pointer finds an even number, it's swapped with the element at `insertPos`, and `insertPos` is incremented. If an odd number is found, we just continue, as it will eventually be swapped out of the even partition when a later even number is found.

```java
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int insertPos = 0; // Pointer for the next even number's position
        for (int current = 0; current < nums.length; current++) {
            // If we find an even number
            if (nums[current] % 2 == 0) {
                // Swap it with the element at insertPos
                int temp = nums[insertPos];
                nums[insertPos] = nums[current];
                nums[current] = temp;
                
                // Move the insert position for the next even number
                insertPos++;
            }
        }
        return nums;
    }
}
```
Another popular two-pointer variant uses `left` and `right` pointers moving towards each other, which is also equally efficient.
### Algorithm
- Initialize `insertPos = 0`. This pointer marks the end of the subarray of even numbers.
- Iterate through the array with a `current` pointer from `0` to `nums.length - 1`.
- At each element `nums[current]`, check if it's even.
- If `nums[current]` is even, swap it with the element at `nums[insertPos]`.
- After the swap, increment `insertPos`.
- If `nums[current]` is odd, do nothing and simply move to the next element.
- After the loop finishes, the array is correctly partitioned.

# Solutions
### Java

```java
class Solution {
public
  int[] sortArrayByParity(int[] nums) {
    int i = 0, j = nums.length - 1;
    while (i < j) {
      if (nums[i] % 2 == 0) {
        ++i;
      } else if (nums[j] % 2 == 1) {
        --j;
      } else {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        ++i;
        --j;
      }
    }
    return nums;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var sortArrayByParity =
  function (nums) {
    for (let i = 0, j = nums.length - 1; i < j; ) {
      if (nums[i] % 2 === 0) {
        ++i;
      } else if (nums[j] % 2 === 1) {
        --j;
      } else {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        ++i;
        --j;
      }
    }
    return nums;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> sortArrayByParity(vector<int> &nums) {
    int i = 0, j = nums.size() - 1;
    while (i < j) {
      if (nums[i] % 2 == 0) {
        ++i;
      } else if (nums[j] % 2 == 1) {
        --j;
      } else {
        swap(nums[i++], nums[j--]);
      }
    }
    return nums;
  }
};

```

### Python

```python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]: i, j = 0, len(nums) - 1 while i < j: if nums[i] % 2 == 0: i += 1 elif nums[j] % 2 == 1: j -= 1 else: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 return nums

```