[Python] O(n) In place partition, explained
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 pointe
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.\n\n1. Step 1: A = [4, 10, 2, 3, 7, 7, 8, 2, 1, **1**], `beg = 0`, `end = 8`\n2. Step 2: A = [**4**, 10, 2, 3, 7, 7, 8, 2, 1, **1**], `beg = 1`, `end = 8`\n3. Step 3: A = [**4, 10**, 2, 3, 7, 7, 8, 2, 1, **1**], `beg = 2`, `end = 8`\n4. Step 4:  A = [**4, 10, 2**, 3, 7, 7, 8, 2, 1, **1**],  `beg = 3`, `end = 8`\n5. Step 5:  A = [**4, 10, 2**, 1, 7, 7, 8, 2, **3, 1**],  `beg = 3`, `end = 7`\n6. Step 6:  A = [**4, 10, 2**, 2, 7, 7, 8, **1, 3, 1**],  `beg = 3`, `end = 6`\n7. Step 7:  A = [**4, 10, 2, 2**, 7, 7, 8, **1, 3, 1**],  `beg = 4`, `end = 6`\n8. Step 8:  A = [**4, 10, 2, 2**, 8, 7, **7, 1, 3, 1**],  `beg = 4`, `end = 5`\n9. Step 9:  A = [**4, 10, 2, 2, 8**, 7, **7, 1, 3, 1**],  `beg = 5`, `end = 5`\n10. Step 10:  A = [**4, 10, 2, 2, 8, 7, 7, 1, 3, 1**], `beg = 5`, `end = 4`\n\n**Complexity**: Time complexity is `O(n)`, space complexity is `O(1)`, because we do all in place.\n\nNote 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.\nhttps://leetcode.com/problems/sort-colors/discuss/681526/Python-O(n)-3-pointers-in-place-approach-explained\n\n```\nclass Solution:\n    def sortArrayByParity(self, A):\n        beg, end = 0, len(A) - 1\n        \n        while beg <= end:\n            if A[beg] % 2 == 0:\n                beg += 1\n            else:\n                A[beg], A[end] = A[end], A[beg]\n                end -= 1\n        return A\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Two Pointers']