905. Sort Array By Parity

1. Description

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.

2. Example

Example 1:
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:
Input: nums = [0]
Output: [0]

3. Constraints

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

4. Solutions

Two Pointers

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    vector<int> sortArrayByParity(vector<int> nums) {
        for (int left = 0, right = nums.size() - 1; left < right; ++left, --right) {
            while (left < right && (nums[left] & 1) == 0) {
                ++left;
            }

            while (left < right && (nums[right] & 1) == 1) {
                --right;
            }

            swap(nums[left], nums[right]);
        }

        return nums;
    }
};