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

One way to solve this problem is to just sort data or use additional memory. However, there is better approach without using additional memory, using two pointers. The idea is to have two pointers: beg and end, where beg points just after the group of formed even elements in the beginning and end points just before group of odd elements in the end. Let us consider example: A = [1,10,2,3,7,7,8,2,1,4]. On each step I show current A, beg and end. I denote by bold font numbers which are already on place.

  1. Step 1: A = [4, 10, 2, 3, 7, 7, 8, 2, 1, 1], beg = 0, end = 8
  2. Step 2: A = [4, 10, 2, 3, 7, 7, 8, 2, 1, 1], beg = 1, end = 8
  3. Step 3: A = [4, 10, 2, 3, 7, 7, 8, 2, 1, 1], beg = 2, end = 8
  4. Step 4: A = [4, 10, 2, 3, 7, 7, 8, 2, 1, 1], beg = 3, end = 8
  5. Step 5: A = [4, 10, 2, 1, 7, 7, 8, 2, 3, 1], beg = 3, end = 7
  6. Step 6: A = [4, 10, 2, 2, 7, 7, 8, 1, 3, 1], beg = 3, end = 6
  7. Step 7: A = [4, 10, 2, 2, 7, 7, 8, 1, 3, 1], beg = 4, end = 6
  8. Step 8: A = [4, 10, 2, 2, 8, 7, 7, 1, 3, 1], beg = 4, end = 5
  9. Step 9: A = [4, 10, 2, 2, 8, 7, 7, 1, 3, 1], beg = 5, end = 5
  10. Step 10: A = [4, 10, 2, 2, 8, 7, 7, 1, 3, 1], beg = 5, end = 4

Complexity: Time complexity is O(n), space complexity is O(1), because we do all in place.

Note also, that this problem is special case of problem 75: Sort Colors, where we need to partition in three parts, here we have only two. See my post, explaing this problem.

class Solution:
    def sortArrayByParity(self, A):
        beg, end = 0, len(A) - 1
        
        while beg <= end:
            if A[beg] % 2 == 0:
                beg += 1
            else:
                A[beg], A[end] = A[end], A[beg]
                end -= 1
        return A

If you like the solution, you can upvote it on leetcode discussion section: Problem 0905