BL
U

34. Separate Even and Odd Elements Preserving Order

Easy

Problem Description

Rearrange an array of NN integers so that all even numbers appear first, followed by all odd numbers. The relative order among even elements and among odd elements must be preserved.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the NN space-separated integers after rearrangement.

Example 1:
Input:
6
1 2 3 4 5 6
Output:
2 4 6 1 3 5
Explanation: Even numbers (2, 4, 6) first, followed by odds (1, 3, 5).
Example 2:
Input:
3
2 4 6
Output:
2 4 6
Explanation: All even numbers remain unchanged.
Example 3:
Input:
3
1 3 5
Output:
1 3 5
Explanation: All odd numbers remain unchanged.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online