PIVOT! PIVOOOTTT!  Two Pointers (Dutch National Flag Problem)  | Time O(n) and space O(1)
Here, only the parity of the numbers in the arrays matters so, we can consider these elements as binary elements. 0 for even parity and 1 for odd parity. So our
Here, only the parity of the numbers in the arrays matters so, we can consider these elements as binary elements. 0 for even parity and 1 for odd parity. So our problems now boils down to sorting a binary array. We could just sort the array which would take O(nlogn) time. But we could do this more efficiently using the [dutch national flag problem](https://en.wikipedia.org/wiki/Dutch_national_flag_problem) but instead of three type of elements we just have two here.\n\n\nBut how exactly does this work. How could we sort a binary array in just O(n) time. Let us try to understand.\n\nWe idea is somewhat similar to Insertion sort where we have a pivot element and consider every element to the left of it sorted in non-decreasing order. We could use this idea to quickly sort the binary array.\n\n![image](https://assets.leetcode.com/users/images/a6994263-c40c-4feb-9712-a62a8e38b2cd_1651470068.613384.png)\n\nWe consider an hypothetical index which would act like a pivot and every element to the left of it is an even number and every element to the right of it is an odd number, but if we find any element that is not following this then we can swap them to establish the order.\n\nHere is the implementation of the above idea.\n\n```\nclass Solution:\n    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n        \n\t\t#Initially the pivot is at the end\n        pivot = len(nums)-1\n        \n\t\t#we start from the 0th index\n        i = 0\n\t\t\n\t\t#As long as we are to the left of the pivot we only need all even numbers\n        while i <= pivot:\n            \n\t\t\t#If we find a number that is not even then...\n            if nums[i]%2 != 0:\n\t\t\t\t# We swap it out with the pivot element and then decrease the pivot index as now we have only odd numbers to the right of the pivot\n                nums[i], nums[pivot] = nums[pivot], nums[i]\n                pivot-=1\n            else:\n\t\t\t#but if the element was even then we just move forward\n                i+=1\n        \n        return nums\n```\nThe above approach as easy it might seem, It is best understood with an example.\n\n```\nnums =  3   1   2   4\n\t    0   1   2   3p\n\nInitially the pivot is at the index 3, i.e we assume every element to the left o f 3 is an even number and every element on the right of the pivot is odd.\n\nindex  = 0:\n\tElement = 3, which is odd so we don\'t need it here so we swap it with the pivot index and then decrease the pivot index.\n\tnums =  4   1   2   3\n\t        0   1   2   3\n\t\n\tNow we check if element at index 0 is even, yes it is so we move forward.\n\nindex = 1\n\tElement = 1, which is odd so we swap it and send it to the right of pivot\n\tnums =  4   2   1   3\n\t        0   1p  2   3\n\t\t\t\nNow as out pointer has reached the pivot we can stop the process as we know that every element till the pointer \nelement was even as we deliberately did that and every element to the right of pivot is odd as \nit was the defination of pivot. Hence we sorted the array by parity.\n\n\n```\n\n**Time Complexity**\n\nFor every step we take either the index moves forward or the pivot moves backwards so at most we would have n steps, so the time complexity would be *O(n)*\n\n**Space Complexity**\n\nWe are just using two variables no matter what the size of the array is, hence the space complexity would be *O(1)*
['Two Pointers', 'Python']