Practice/Meta/Leetcode 905. Sort Array By Parity

Leetcode 905. Sort Array By Parity

CodingOptional

Problem

Given an array of integers, rearrange the elements so that all even numbers appear before all odd numbers. The relative order of elements within the even group and within the odd group doesn't matter—any valid arrangement is acceptable.

You should modify the array in-place and return it.

Requirements

1. All even integers must appear before all odd integers in the result
2. The order within the even numbers group can be arbitrary
3. The order within the odd numbers group can be arbitrary
4. Modify the array in-place for optimal space efficiency

Constraints

• 1 ≤ array length ≤ 5000
• 0 ≤ array[i] ≤ 5000
• Aim for O(n) time complexity
• Aim for O(1) extra space complexity (not counting the input array)

Examples

Example 1:

Input: [3, 1, 2, 4] Output: [2, 4, 3, 1] Explanation: All even numbers (2, 4) come before all odd numbers (3, 1). Other valid outputs include [4, 2, 1, 3], [2, 4, 1, 3], etc.

Example 2:

Input: [0] Output: [0] Explanation: A single even number is already correctly partitioned.

Example 3:

Input: [1, 3, 5, 7] Output: [1, 3, 5, 7] Explanation: When all numbers are odd, no rearrangement is needed.

Example 4:

Input: [10, 9, 8, 7, 6, 5] Output: [10, 8, 6, 9, 7, 5] Explanation: Even numbers (10, 8, 6) are grouped before odd numbers (9, 7, 5).