905. Sort Array By Parity – In-place Solution | LeetCode Problem4 min read

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

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

Note:

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

The template code which is already provided on LeetCode:

class Solution {
      public int[] sortArrayByParity(int[] A) {
      }
}

We are going to tackle this problem by 2 different approaches in this article, the first one requires an auxiliary to solve the problem, the second one we try a different way and solve the problem in-place using Java.

The First Approach

In Java, the first approach we can come up with is to sort the array based on parity, then getting the array after sorting then we’re done. We can use the sort function of the Arrays class for this purpose, however, the sort function takes an array of generic type T[] to be sorted, and the Comparator which we pass in the sort function to perform custom sort also needs an argument type T. Hence, before sorting, we must create an auxiliary array with the type of Integer[] and copy all elements on the provided array to this array:

Integer [] nums = new Integer[A.length];
for(int i = 0; i < A.length; i++) {
    nums[i] = A[i];
}

Then now we fulfill the custom sorting function in the array we’ve just created:

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

By doing this custom sort, the even element is always placed before the odd one. We can also utilize the compareInt method:

Arrays.sort(nums, Comparator.comparingInt(a -> a % 2));

After we have the array that satisfies the problem, we then need to copy its elements back to the original array because here the int[] needs returning:

for(int i = 0; i < nums.length; i++) {
    A[i] = nums[i];
}
return A;

The complete code for the first approach:

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

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

     for (int i = 0; i < A.length; i++)
          A[i] = nums[i];
     return A;
}

Time complexity: O(n) – where n is the size of the array
Space complexity: O(n) – where n is the size of the original array.

The second approach – In-place

In the second approach, we will try to find a way to modify the array in-place, which means no auxiliary data structure is needed for solving this problem.

To do that, we create 2 pointers, one starts at the beginning moving forward (named i) and one moves backward from the end (named j). The invariant here is everything precedes i must be even, and everything behinds j should be odd. There are 4 cases that (A[i] % 2, A[j] % 2) has:

• If it is (0, 1) then we know that A[i] is even and A[j] is odd, they are correct order then we move on: i++, j--.
• If it is (1, 0) then we know they are in the reverse order, we simply swap them and move on.
• If it is (0, 0) then only A[i] is correct, then i++.
• If it is (1, 1) then only A[j] is correct, then we move to the next j position, j--.

We continue this process while i is less than j. When they are equal, we know we go through all elements and then we can stop:

public int[] sortArrayByParity(int[] A) {
      int i = 0, j = A.length - 1; // 2 pointers
      while (i < j) {
           if (A[i] % 2 > A[j] % 2) { // if both a[i] and a[j]   are in the incorrect positions, then swap
           int tmp = A[i];
           A[i] = A[j];
           A[j] = tmp;
           }
      if (A[i] % 2 == 0) i++; // if a[i] is in correct position, then move the next one
      if (A[j] % 2 == 1) j--; // if a[j] is in the correct position, the move to the next one.
      }
      return A; // array after sorted
}

Time Complexity: O(n) – where n is the size of the array.
Space Complexity: O(1) – we haven’t had to create any auxiliary data structure and just return the original array after being modified.