Partition Even Odd — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, produce a new ordering where every element that originally occupied an even index (0‑based) comes before any element that originally occupied an odd index. The internal order of the even‑indexed elements must stay the same as in the input, and likewise for the odd‑indexed elements. Return the reordered array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Partition Even Odd"
WHY DOES IT MATTER?
Stable partitioning appears frequently when data must be reorganized without losing chronological or priority information—think log processing, UI rendering queues, or batch job scheduling where original order matters within categories.
OPTIMIZATION CHALLENGE
The insight is to avoid moving elements repeatedly; by simply recording the indices (or values) of even‑positioned items in a first pass and odd‑positioned items in a second pass, you achieve linear time while preserving order, eliminating the costly element‑by‑element swaps of naïve methods.
REAL-WORLD CONNECTION
Imagine a conveyor belt where items placed at even positions must be shipped first, but the order they arrived on the belt must stay intact; you’d divert even‑positioned items into one bin and odd‑positioned items into another, then ship the bins sequentially—mirroring the two‑list buffer technique.
During an interview, write the two‑list solution first to guarantee correctness and stability, then discuss possible in‑place optimizations only if the interviewer explicitly asks for O(1) space.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The task is essentially a stable partition of an array based on the parity of the original indices. A stable partition preserves the relative order of elements within each group, which distinguishes this problem from a simple even‑odd value partition. A naïve solution might iterate over the array for each index, repeatedly swapping elements to bring even‑indexed items forward; this quickly degrades to O(n²) because each swap can disturb previously placed elements and requires rescanning. The optimal paradigm leverages a single linear scan, collecting even‑indexed elements into one buffer and odd‑indexed elements into another, then concatenating them. This approach guarantees O(n) time because each element is visited exactly once, and O(n) auxiliary space to hold the two buffers, which is optimal for a stable reorder without in‑place tricks that would otherwise increase time complexity.
Interview Questions on This Problem
Q1How would you modify the solution if the requirement changed to preserve the original order of values that are even versus odd (based on value, not index)?
Collect values that are even into one list and odd values into another while iterating once, then concatenate; this is also a stable partition with O(n) time and O(n) space.
Q2Can you achieve the same ordering in‑place with O(1) extra space? What trade‑offs arise?
In‑place stable partition can be done using rotation algorithms (e.g., block swap) but it requires O(n²) time or complex O(n) time with O(1) space using recursive divide‑and‑conquer, which is harder to implement and error‑prone; most interview settings accept O(n) extra space for simplicity.
Q3Why is a two‑pointer approach (one reading, one writing) insufficient for this problem when stability is required?
A two‑pointer method that swaps elements when a mismatch is found changes the relative order of the even‑indexed elements, violating the stability constraint; it only works for unordered partitions.
Examples
Input
[5,2,8,6,3,9]
Output
[5,8,3,2,6,9]
Explanation: Indices 0,2,4 hold 5,8,3 – they are placed first preserving order. Indices 1,3,5 hold 2,6,9 – they follow, also in original order.
Input
[10]
Output
[10]
Explanation: The sole element is at index 0 (even), so the result is identical to the input.
Input
[7,1,4,2,9]
Output
[7,4,9,1,2]
Explanation: Even indices 0,2,4 give 7,4,9; odd indices 1,3 give 1,2. Concatenating yields the output while keeping each group’s order.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- Solution must run in O(n) time where n is nums.length
- Only O(1) additional space beyond the output array is allowed
Optimal Approach & Strategy
Perform a single pass, collect even‑indexed elements into one buffer and odd‑indexed into another, then merge them, achieving linear time.
Brute Force Approach
Repeatedly scan the array, swapping out‑of‑place elements until all even‑indexed items are at the front, which leads to quadratic time.
Verified Code Solutions
function partitionEvenOdd(nums) {
const evens = [];
const odds = [];
for (let i = 0; i < nums.length; ++i) {
if (i % 2 === 0) evens.push(nums[i]);
else odds.push(nums[i]);
}
return evens.concat(odds);
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const nums = data.slice(1, 1 + n);
const res = partitionEvenOdd(nums);
console.log(res.join(' '));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<int> partitionEvenOdd(const vector<int>& nums) {
vector<int> evens, odds;
evens.reserve((nums.size()+1)/2);
odds.reserve(nums.size()/2);
for (size_t i = 0; i < nums.size(); ++i) {
if (i % 2 == 0) evens.push_back(nums[i]);
else odds.push_back(nums[i]);
}
evens.insert(evens.end(), odds.begin(), odds.end());
return evens;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;if(!(cin>>n))return 0;vector<int>a(n);for(int i=0;i<n;++i)cin>>a[i];auto res=partitionEvenOdd(a);for(size_t i=0;i<res.size();++i){if(i)cout<<' ';cout<<res[i];}cout<<'\n';return 0;}import java.io.*;
import java.util.*;
public class Main {
public static List<Integer> partitionEvenOdd(List<Integer> nums) {
List<Integer> evens = new ArrayList<>();
List<Integer> odds = new ArrayList<>();
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) evens.add(nums.get(i));
else odds.add(nums.get(i));
}
evens.addAll(odds);
return evens;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
List<Integer> nums = new ArrayList<>();
int count = 0;
while (count < n) {
StringTokenizer st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens() && count < n) {
nums.add(Integer.parseInt(st.nextToken()));
count++;
}
}
List<Integer> res = partitionEvenOdd(nums);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(res.get(i));
}
System.out.println(sb.toString());
}
}def partition_even_odd(nums):
evens = []
odds = []
for i, v in enumerate(nums):
if i % 2 == 0:
evens.append(v)
else:
odds.append(v)
return evens + odds
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
res = partition_even_odd(nums)
print(' '.join(map(str, res)))
if __name__ == '__main__':
main()function partitionEvenOdd(nums) {
const evens = [];
const odds = [];
for (let i = 0; i < nums.length; ++i) {
if (i % 2 === 0) evens.push(nums[i]);
else odds.push(nums[i]);
}
return evens.concat(odds);
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const nums = data.slice(1, 1 + n);
const res = partitionEvenOdd(nums);
console.log(res.join(' '));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.