Leetcode Problem 905 : Sort array by parity

This problem[1] asks us to sort an array of numbers into odd and even numbers. For e.g.,

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.

The simplest way to solve this problem would be to introduce a new array and iterate through the original array to store even and odd numbers in order in the new array. But, that would lead to an additional space complexity of O(n). In-place sorting would no longer lead to an O(n) space complexity.

We can use two pointers to perform in- place sorting. One of the pointers points to the beginning of the array and the second pointer points to the end of the array.

public int[] sortArrayByParity(int[] A) {
        int ptrStart = 0, ptrEnd = A.length - 1;
        while(ptrStart < ptrEnd) {
            if(A[ptrStart]%2 != 0 && A[ptrEnd]%2 == 0) {
                int temp = A[ptrStart];
                A[ptrStart] = A[ptrEnd];
                A[ptrEnd] = temp;
            }
            if(A[ptrStart] % 2 == 0)
                ptrStart++;
            if(A[ptrEnd] % 2 != 0)
                ptrEnd--;
        }
        return A;
    }

If the number at the start of the array is even, we go on to the next index. Else, we swap the odd number with an even number at the end of the array.

The time complexity for this solution is O(n) and the space complexity is O(1).