Sort Array By Parity

Problem Statement

In this task, you are provided with an integer array nums. The goal is to rearrange the elements of this array such that all even integers appear before any odd integers. It's important to note that the exact sequence of even and odd numbers doesn't matter, as long as all evens are before any odds. The solution is flexible in terms of the internal order of the even and odd numbers. Therefore, you may return any valid configuration that meets these criteria.

Examples

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]

Constraints

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

Approach and Intuition

The problem revolves around segregating even and odd integers in an array, placing all even integers first, followed by the odd integers. The constraints and examples suggest this can be achieved without altering the relative order of the numbers within their respective (even or odd) groups, but keeping any particular order is not a strict requirement.

Steps to Approach:

1. Initialize two pointer variables, one at the start (left) and one at the end (right) of the array.
2. Use a loop to traverse the array:
   • If the current number at the left pointer is even, move the left pointer one step to the right, as it is already in a correct position.
   • If the current number is odd, check the number at the right pointer:
     • If it is even, swap the numbers at left and right.
     • Move the right pointer one step to the left.
     • Continue this process until the left pointer exceeds or meets the right pointer.
3. The above process ensures that all even numbers gather towards the beginning of the array and all odds towards the end, fulfilling the problem's requirement.

Both the problem constraints:

• the maximum size of the array is 5000,
• integer values ranging from 0 to 5000,

ensure that the segregation can be achieved efficiently even with a straightforward approach, as detailed above.

Solutions

class Solution {
    public int[] arrangeEvenOdd(int[] values) {
        int start = 0, end = values.length - 1;
        while (start < end) {
            if (values[start] % 2 > values[end] % 2) {
                int temp = values[start];
                values[start] = values[end];
                values[end] = temp;
            }
    
            if (values[start] % 2 == 0) start++;
            if (values[end] % 2 == 1) end--;
        }
    
        return values;
    }
}