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.

Example 1:

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

Example 2:

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

Constraints:

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

Solution

The important point for this problem is that the order of array elements do not matter. The only point is that even numbers need to be before odd numbers. In this case, we can use two pointers, one from left and another from right. If we find a number which is even from left, we simply increment left. If it’s odd and at the same time if the number on the right pointer is even, swap the numbers at nums[left] and nums[right] and move both pointers. If the number at right is already odd, then simply increment right.

 1class Solution {
 2    public int[] sortArrayByParity(int[] nums) {
 3        if (nums == null || nums.length == 0)
 4            return nums;
 5        int left = 0, right = nums.length - 1;
 6        while (left < right) {
 7            if (nums[left] % 2 == 0) {
 8                left++;
 9            } else if (nums[right] % 2 == 0){
10                int temp = nums[right];
11                nums[right--] = nums[left];
12                nums[left++] = temp;
13            } else {
14                right--;
15            }
16        }
17        return nums;
18    }
19}
  • Time Complexity: O(n)
  • Space Complexity: O(1)