[C++] Three O(n) Solutions
Solution #1: Two-pass solution using two-pointer technique [O(n) Time & O(1) Space]\n\nvector<int> sortArrayByParityII(vector<int>& nums) {\n\tfor (int i = 0, c
**Solution #1:** Two-pass solution using two-pointer technique [O(n) Time & O(1) Space]\n```\nvector<int> sortArrayByParityII(vector<int>& nums) {\n\tfor (int i = 0, c = 0; i < nums.size(); i++) {\n\t\tif (nums[i] % 2 != 0) c++;\n\t\telse if (c > 0) swap(nums[i], nums[i - c]);\n\t}\n\tfor (int i = 1; i < nums.size() / 2; i += 2) swap(nums[i], nums[nums.size() - i - 1]);\n\treturn nums;\n}\n```\n\n**Solution #2:** One-pass solution using two-pointer technique [O(n) Time & O(1) Space]\n```\nvector<int> sortArrayByParityII(vector<int>& nums) {\n\tint i = 0, j = nums.size() - 1;\n\twhile (i < nums.size() && j >= 0) {\n\t\tif (nums[i] % 2 == 0) i += 2;\n\t\telse if (nums[j] % 2 != 0) j -= 2;\n\t\telse swap(nums[i], nums[j]);\n\t}\n\treturn nums;\n}\n```\n\n**Solution #3:** One-pass solution [O(n) Time & O(n) Space] \n```\nvector<int> sortArrayByParityII(vector<int>& nums) {\n\tvector<int> result(nums.size());\n\tfor (int i = 0, j = 0, k = 1; i < nums.size(); i++) {\n\t\tif (nums[i] % 2 == 0) {\n\t\t\tresult[j] = nums[i];\n\t\t\tj += 2;\n\t\t}\n\t\telse {\n\t\t\tresult[k] = nums[i];\n\t\t\tk += 2;\n\t\t}\n\t}\n\treturn result;\n}\n```\n**Note:** Not an in-place solution.
['C']