LeetCode 905: Given an array nums of non-negative integers, return an array comprising all the even elements of nums, followed by all the odd elements of nums.

Input: nums = [3,1,2,4]

Output: [2,4,3,1]

Other accepted answers include [4,2,3,1], [2,4,1,3], and [4,2,1,3].

Please practice this problem on your own and then look at the solutions.

1. Introduction

In this article, I will discuss how to sort an array by parity, which means moving all even numbers to left and odd numbers to right. Specifically, I will discuss 4 different ways to achieve the solution. I will explain all solutions with time and space complexity.

2. Content

The 4 different ways to sort an array by parity are:

1. Create an auxiliary array and copy even and then odd numbers into it.
2. Using Stream API and custom Comparator.
3. Two pointer approach: Maintain an index on odd number and even number, respectively.
4. Two pointer approach: Move one pointer from start to end and other pointer from end to start.

3. Create an auxiliary array and copy even and then odd numbers into it.

The idea is simple here. 

• You can create an auxiliary array called result. The size of this array is equal to the size of the input array. 
• Iterate through the input array and copy all even numbers to result.
• Then iterate again through the input array and copy all odd numbers to result.
• Return the result array.

public int[] sortArrayByParity(int[] arr) {
	int[] result = new int[arr.length];
	int resultIndex = 0;
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] % 2 == 0) {
			result[resultIndex] = arr[i];
			resultIndex++;
		}
	}
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] % 2 != 0) {
			result[resultIndex] = arr[i];
			resultIndex++;
		}
	}
	return result;
}

Time Complexity: We iterate through the array twice, which makes the time complexity O(2n). We can ignore the constant so the final time complexity is O(n) where n is the number of elements in the array.

Space Complexity: As we are creating a result array, i.e. using auxiliary space, we are using more space. This space is equal to the number of input array elements. So space complexity is O(n) where n is the number of elements in the array.

4. Using Stream API and custom Comparator

We can use Stream API and a custom Comparator to achieve the result too. How? If we mod the number by 2, even numbers have a remainder of 0 and odd numbers have a remainder of 1.

So our Comparator can be like this:

Comparator<Integer> comp = (a, b) -> Integer.compare(a % 2, b % 2)

Comparator<Integer> comp = (a, b) -> Integer.compare(a % 2, b % 2)

public int[] sortArrayByParityUsingStream(int[] arr) {
	return 
		Arrays
		.stream(arr)
		.boxed()
		.sorted((a, b) -> Integer.compare(a % 2, b % 2))
		.mapToInt(Integer::intValue)
		.toArray();
}

Time Complexity: As we are using the sorted() method of Stream API, we can assume the fact that the sorting will take O(n log n). And it will also iterate the entire array. So the total time taken is O(n log n) + O(n). This makes final time complexity O(n log n).

Space Complexity: The Stream API will return the result in a new array. So space complexity is O(n) where n is the number of elements in the array.

5. Two pointer approach: Maintain an index on odd number and even number, respectively.

This technique is a little different from the other that I discussed. In this technique, we will just play with pointers. 

• Assume that the first element, index 0, is odd. We will swap the element with this index only if we encounter the even element. 
• If all elements are even, it will end up swapping elements with itself. 

public int[] sortArrayByParity(int[] arr) {
	int oddIndex = 0;
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] % 2 == 0) {
			int temp = arr[i];
			arr[i] = arr[oddIndex];
			arr[oddIndex] = temp;
			oddIndex++;
		}
	}
	return arr;
}

Time Complexity: We just iterate through the array once. So the time complexity O(n log n).

Space Complexity: We aren’t using any auxiliary space, so the space complexity is O(1).

6. Two pointer approach: Move one pointer from start to end and other pointer from end to start.

In the previous technique, we were doing unnecessary swapping, if all the elements are even. We can just skip the elements that are in the right place and swap only if needed.

public int[] sortArrayByParity(int[] nums) {
	int i = 0;
	int j = nums.length - 1;
        
	while(i < j) {
		while(i < nums.length && nums[i] % 2 == 0) i++;
		while(j >= 0 && nums[j] % 2 != 0) j--;
		if(i < j) {
			int temp = nums[i];
			nums[i] = nums[j];
			nums[j] = temp;
		}
	}
	return nums;
}   

7. Conclusion

In this article, we saw how we are sort the array by parity. Code: GitHub.