LeetCode 922 - Sort Array By Parity II

https://leetcode.com/problems/sort-array-by-parity-ii/

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

https://leetcode.com/problems/sort-array-by-parity-ii/discuss/181500/Java-Two-pointers-inplace-O(n)-time-simple-and-straightforward

Use i and j to denote even and odd indices, respectively.
Loop through input array,

1. locate next wrongly placed item with odd index j;
2. if current even-index item, A[i], is wrongly placed, swap it with A[j]; otherwise, forward to the next even index;

public int[] sortArrayByParityII(int[] A) {
        int e = 0;
        int o = 1;
        
        while(e < A.length && o < A.length) {
            if(A[e]%2 != 0) {
                swap(A, e, o);
                o += 2;
            } else {
                e += 2;
            }
        }

        return A;
    }

https://leetcode.com/problems/sort-array-by-parity-ii/discuss/181160/Java-two-pointer-one-pass-inplace

    public int[] sortArrayByParityII(int[] A) {
        int i = 0, j = 1, n = A.length;
        while (i < n && j < n) {
            while (i < n && A[i] % 2 == 0) {
                i += 2;
            }
            while (j < n && A[j] % 2 == 1) {
                j += 2;
            }
            if (i < n && j < n) {
                swap(A, i, j);
            }
        }
        return A;
    }
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }




Approach 2: Read / Write Heads

We are motivated (perhaps by the interviewer) to pursue a solution where we modify the original array A in place.

First, it is enough to put all even elements in the correct place, since all odd elements will be in the correct place too. So let's only focus on A[0], A[2], A[4], ...

Ideally, we would like to have some partition where everything to the left is already correct, and everything to the right is undecided.

Indeed, this idea works if we separate it into two slices even = A[0], A[2], A[4], ... and odd = A[1], A[3], A[5], .... Our invariant will be that everything less than i in the even slice is correct, and everything less than j in the odd slice is correct.

Algorithm

For each even i, let's make A[i] even. To do it, we will draft an element from the odd slice. We pass jthrough the odd slice until we find an even element, then swap. Our invariant is maintained, so the algorithm is correct.

  public int[] sortArrayByParityII(int[] A) {

    int j = 1;

    for (int i = 0; i < A.length; i += 2)

      if (A[i] % 2 == 1) {

        while (A[j] % 2 == 1)

          j += 2;

        // Swap A[i] and A[j]

        int tmp = A[i];

        A[i] = A[j];

        A[j] = tmp;

      }

    return A;

  }

Approach 1: Two Pass

Read all the even integers and put them into places ans[0], ans[2], ans[4], and so on.

Then, read all the odd integers and put them into places ans[1], ans[3], ans[5], etc.

  public int[] sortArrayByParityII(int[] A) {

    int N = A.length;

    int[] ans = new int[N];

    int t = 0;

    for (int x : A)

      if (x % 2 == 0) {

        ans[t] = x;

        t += 2;

      }

    t = 1;

    for (int x : A)

      if (x % 2 == 1) {

        ans[t] = x;

        t += 2;

      }

    return ans;

  }