C++ O(n) time O(1) space solution with intuition for building the solution
Basic Idea of Question\nWe are given an array in which half of the numbers are odd, and the other half are even. So the length of the array is always even, and 
## Basic Idea of Question\nWe are given an array in which half of the numbers are odd, and the other half are even. So the length of the array is always even, and the first index is even (0), while the last index is odd (n-1). We have to arrange the numbers in the array such that at every even index, there is an even number, while at every odd index, there is an odd number.\n\nThe most naive solution to this question is to just traverse the array, and upon finding an out-of-place element, find its replacement in the array by traversing the subarray after it. This algorithm will cost us **O(n<sup>2</sup>)** in time and **O(1)** in space, but it isn\'t enough. It just seems too naive of a solution.\n<br>\n\n## Approach 1: Separate even and odd numbers\nThe next approach that might come to mind is to just iterate over the array and separate the numbers into two groups, even and odd.\nThen we build the array again from the start by choosing an even number for each even index and an odd number for each odd index.\nThis is a good solution, and it does fit in with the least runtime possible for such an algorithm, which is **O(n)** since we have to at least check every element, so that they are all at their place, but it also requires extra space of O(n) for storing the even and odd numbers.\n\nThe code for the approach is as follows:\n```\nvector<int> sortByParityII(vector<int>& nums) {\n\tint n = nums.size();\n\tvector<int> evens, odds;\n\tevens.reserve(n/2);\n\todds.reserve(n/2);\n\tfor(int i = 0; i<n; i++) {\n\t\tif(nums[i] % 2 == 0) {\n\t\t\tevens.push_back(nums[i]);\n\t\telse {\n\t\t\todds.push_back(nums[i]);\n\t}\n\t//filling even spaces\n\tfor(int i = 0; i<n; i+=2) {\n\t\tnums[i] = evens[i/2];\n\t}\n\t//filling odd spaces\n\tfor(int i = 1; i<n; i+=2) {\n\t\tnums[i] = odds[i/2];\n\t}\n\treturn nums;\n}\n```\nIf you are confused by the lines ```evens.reserve(n/2)``` and ```odds.reserve(n/2)```, they are just ensuring beforehand that our vectors have adequate capacities, so that all push back operations are completed in O(1).\n\n**Time: O(n)** as we just iterate the array two times.\n**Space: O(n)**, the extra space required for the two arrays.\n<br>\n\n## Approach 2: Swap outliers\nWe can think of this question in another way as well. Since the number of even and odd numbers in the array is equal, if there is one outlier (even number at odd index or vice versa), there must be another outlier somewhere, since if there isn\'t, then this place has no rightful element which can fill it.\nIf we find and swap such pairs, we wouldn\'t have to care about finding the odd or even numbers and separating them. In fact, we can even do it in one iteration only, using two pointers.\n\nComing back to the question statement, as n is even,, so index 0 is even and the index (n-1) is odd. So starting at index 0 for the even pointer, and n-1 for the odd pointer would be just fine.\nWe follow the below algorithm until one of the pointers reaches the other end of the array (here i represents the even pointer, and j represents the odd pointer):\n\n1. Keep incrementing i by 2 until either it reaches the other end, or an outlier (odd number at even index).\n2. Keep decrementing j by 2 until either it reaches the other end, or an outlier (even number at odd index).\n3. Swap nums[i] and nums[j]\n\nYou might be thinking, what happens if i stops at an outlier and j reaches the other end, or vice versa?\nWell, the fact that n is even, and there being equal number of even and odd numbers prevents that situation from happening (as explained above). If there will be a pair, it will be a valid pair, otherwise both of them will reach the ends.\n\nThe code for this approach is as follows:\n```\nvector<int> sortByParityII(vector<int>& nums) {\n\tint n = nums.size();\n\tint i = 0, j = n-1;\n\twhile(i<n) {\n\t\twhile(i<n && nums[i]%2==0) i+=2;\n\t\tif(i==n) break;\n\t\twhile(j>=0 && nums[j]%2==1) j-=2;\n\t\t//swap the outliers\n\t\tswap(nums[i], nums[j]);\n\t}\n\treturn nums;\n}\n```\n\n**Time: O(n)** as we traverse the array once.\n**Space: O(1)** as we only use two pointers, and no other space.\n\n<br>\n\n**Don\'t forget to upvote** if you liked this post and learned something from it, and feel free to ask any doubts, or suggest any corrections/improvements in the comments.\n\n\n
['Two Pointers', 'C']