Partition Array by Parity

🎯

Partition Array by Parity

easyTWO_POINTERAmazon

Imagine sorting a line of people so that all those wearing red shirts stand before those wearing blue shirts, without caring about the order within each group.

💡 This problem is a classic example of partitioning an array based on a condition. Beginners often struggle because they try to sort the array fully or use extra space unnecessarily, instead of using two pointers to rearrange elements in-place efficiently.

📋

Problem Statement

Given an integer array nums, reorder it so that all even integers come before all odd integers. Return any array that satisfies this condition.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^9

💡

Example

Input"[3,1,2,4]"

Output[4,2,1,3]

One valid output is [4,2,1,3] where all even numbers (4,2) appear before odd numbers (1,3). The order within evens or odds does not matter.

• Array with all even numbers → output is the same array
• Array with all odd numbers → output is the same array
• Array with one element → output is the same array
• Array with alternating even and odd numbers → output rearranges to group evens first

⚠️

Common Mistakes

Swapping elements without checking pointers cross

Leads to infinite loop or incorrect partition

✅ Always check left < right before swapping

Using extra space when in-place is required

Suboptimal solution rejected by interviewer

✅ Learn two pointers in-place partitioning

Not incrementing pointers correctly after swap

May cause infinite loops or missed elements

✅ Increment both pointers after swapping

Assuming order of evens or odds must be preserved

Overcomplicates solution or wastes time

✅ Clarify problem requirements; if order matters, use stable partition

🧠

Brute Force (Using Extra Array)

💡 This approach is straightforward and helps beginners understand the problem by separating evens and odds explicitly, but it uses extra space and is not optimal.

Intuition

Collect all even numbers first, then all odd numbers, and combine them to form the result.

Algorithm

1. Create two empty lists: one for even numbers and one for odd numbers.
2. Traverse the input array and append each number to the appropriate list based on parity.
3. Concatenate the even list followed by the odd list.
4. Return the concatenated list.

💡 This method is easy to visualize but uses extra space and requires two passes over the data.

</>

Code

from typing import List

def partitionArrayByParity(nums: List[int]) -> List[int]:
    evens = []
    odds = []
    for num in nums:
        if num % 2 == 0:
            evens.append(num)
        else:
            odds.append(num)
    return evens + odds

# Driver code
if __name__ == '__main__':
    print(partitionArrayByParity([3,1,2,4]))  # Output: [2,4,3,1] or any valid partition

Line Notes

evens = []Initialize list to collect even numbers separately

odds = []Initialize list to collect odd numbers separately

for num in nums:Traverse each element to classify by parity

if num % 2 == 0:Check if current number is even

evens.append(num)Add even number to evens list

else:If not even, number is odd

odds.append(num)Add odd number to odds list

return evens + oddsConcatenate evens and odds to form final partitioned array

import java.util.*;

public class PartitionArrayByParity {
    public static int[] partitionArrayByParity(int[] nums) {
        List<Integer> evens = new ArrayList<>();
        List<Integer> odds = new ArrayList<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                evens.add(num);
            } else {
                odds.add(num);
            }
        }
        int[] result = new int[nums.length];
        int index = 0;
        for (int e : evens) {
            result[index++] = e;
        }
        for (int o : odds) {
            result[index++] = o;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] input = {3,1,2,4};
        int[] output = partitionArrayByParity(input);
        System.out.println(Arrays.toString(output)); // Output: [2,4,3,1] or any valid partition
    }
}

Line Notes

List<Integer> evens = new ArrayList<>();Create list to store even numbers separately

List<Integer> odds = new ArrayList<>();Create list to store odd numbers separately

for (int num : nums)Iterate over each element to check parity

if (num % 2 == 0)Check if number is even

evens.add(num);Add even number to evens list

elseIf not even, number is odd

odds.add(num);Add odd number to odds list

int[] result = new int[nums.length];Prepare result array to combine evens and odds

for (int e : evens)Copy even numbers first into result

for (int o : odds)Copy odd numbers after evens

#include <iostream>
#include <vector>

using namespace std;

vector<int> partitionArrayByParity(const vector<int>& nums) {
    vector<int> evens;
    vector<int> odds;
    for (int num : nums) {
        if (num % 2 == 0) {
            evens.push_back(num);
        } else {
            odds.push_back(num);
        }
    }
    evens.insert(evens.end(), odds.begin(), odds.end());
    return evens;
}

int main() {
    vector<int> input = {3,1,2,4};
    vector<int> output = partitionArrayByParity(input);
    for (int num : output) cout << num << ' ';
    cout << endl; // Output: 2 4 3 1 or any valid partition
    return 0;
}

Line Notes

vector<int> evens;Create vector to hold even numbers separately

vector<int> odds;Create vector to hold odd numbers separately

for (int num : nums)Iterate over input array to classify numbers

if (num % 2 == 0)Check parity of current number

evens.push_back(num);Add even number to evens vector

elseIf not even, number is odd

odds.push_back(num);Add odd number to odds vector

evens.insert(evens.end(), odds.begin(), odds.end());Append all odd numbers after evens

return evens;Return combined vector with evens first

function partitionArrayByParity(nums) {
    const evens = [];
    const odds = [];
    for (const num of nums) {
        if (num % 2 === 0) {
            evens.push(num);
        } else {
            odds.push(num);
        }
    }
    return evens.concat(odds);
}

// Test
console.log(partitionArrayByParity([3,1,2,4])); // Output: [2,4,3,1] or any valid partition

Line Notes

const evens = [];Initialize array to collect even numbers

const odds = [];Initialize array to collect odd numbers

for (const num of nums)Loop over each element to check parity

if (num % 2 === 0)Check if number is even

evens.push(num);Add even number to evens array

elseIf not even, number is odd

odds.push(num);Add odd number to odds array

return evens.concat(odds);Concatenate evens and odds arrays to form result

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the array once to separate evens and odds, then combine them, so time is linear. Extra space is used to store evens and odds separately, so space is linear.

💡 For n=100,000 elements, this means about 200,000 operations and extra space for 100,000 elements, which is inefficient for large inputs.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory, so it's good to mention but not ideal to code in interviews.

🧠

Two Pointers (In-Place Partition)

💡 This approach improves space usage by rearranging elements in-place using two pointers, a common technique in partitioning problems.

Intuition

Use two pointers from the start and end of the array to swap misplaced even and odd numbers until pointers meet.

Algorithm

1. Initialize two pointers: left at start, right at end.
2. While left < right, move left forward if nums[left] is even.
3. Move right backward if nums[right] is odd.
4. If nums[left] is odd and nums[right] is even, swap them and move both pointers.
5. Repeat until pointers meet or cross.

💡 This method partitions the array in one pass without extra space, but requires careful pointer movement to avoid errors.

</>

Code

from typing import List

def partitionArrayByParity(nums: List[int]) -> List[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        while left < right and nums[left] % 2 == 0:
            left += 1
        while left < right and nums[right] % 2 == 1:
            right -= 1
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    return nums

# Driver code
if __name__ == '__main__':
    print(partitionArrayByParity([3,1,2,4]))  # Output: [4,2,1,3] or any valid partition

Line Notes

left, right = 0, len(nums) - 1Initialize two pointers at array ends

while left < right:Loop until pointers meet or cross

while left < right and nums[left] % 2 == 0:Move left pointer forward if current is even

while left < right and nums[right] % 2 == 1:Move right pointer backward if current is odd

if left < right:Check if pointers still valid for swapping

nums[left], nums[right] = nums[right], nums[left]Swap misplaced odd and even numbers

left += 1Move left pointer after swap

right -= 1Move right pointer after swap

return numsReturn the partitioned array

import java.util.*;

public class PartitionArrayByParity {
    public static int[] partitionArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 0) left++;
            while (left < right && nums[right] % 2 == 1) right--;
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] input = {3,1,2,4};
        int[] output = partitionArrayByParity(input);
        System.out.println(Arrays.toString(output)); // Output: [4,2,1,3] or any valid partition
    }
}

Line Notes

int left = 0, right = nums.length - 1;Initialize pointers at array boundaries

while (left < right)Loop until pointers meet or cross

while (left < right && nums[left] % 2 == 0) left++;Advance left pointer past evens

while (left < right && nums[right] % 2 == 1) right--;Move right pointer past odds

if (left < right)Check if swap is needed

int temp = nums[left];Store left value temporarily for swap

nums[left] = nums[right];Assign right value to left position

nums[right] = temp;Complete swap by assigning temp to right

left++; right--;Move pointers inward after swap

return nums;Return the rearranged array

#include <iostream>
#include <vector>

using namespace std;

vector<int> partitionArrayByParity(vector<int>& nums) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        while (left < right && nums[left] % 2 == 0) left++;
        while (left < right && nums[right] % 2 == 1) right--;
        if (left < right) {
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }
    return nums;
}

int main() {
    vector<int> input = {3,1,2,4};
    vector<int> output = partitionArrayByParity(input);
    for (int num : output) cout << num << ' ';
    cout << endl; // Output: 4 2 1 3 or any valid partition
    return 0;
}

Line Notes

int left = 0, right = (int)nums.size() - 1;Initialize two pointers at array ends

while (left < right)Loop until pointers cross

while (left < right && nums[left] % 2 == 0) left++;Skip even numbers from left

while (left < right && nums[right] % 2 == 1) right--;Skip odd numbers from right

if (left < right)Check if swap needed

swap(nums[left], nums[right]);Swap misplaced odd and even numbers

left++; right--;Move pointers inward after swap

return nums;Return the partitioned array

function partitionArrayByParity(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        while (left < right && nums[left] % 2 === 0) left++;
        while (left < right && nums[right] % 2 === 1) right--;
        if (left < right) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
            right--;
        }
    }
    return nums;
}

// Test
console.log(partitionArrayByParity([3,1,2,4])); // Output: [4,2,1,3] or any valid partition

Line Notes

let left = 0, right = nums.length - 1;Initialize pointers at array boundaries

while (left < right)Loop until pointers meet or cross

while (left < right && nums[left] % 2 === 0) left++;Move left pointer past evens

while (left < right && nums[right] % 2 === 1) right--;Move right pointer past odds

if (left < right)Check if swap is needed

[nums[left], nums[right]] = [nums[right], nums[left]];Swap odd and even numbers

left++; right--;Move pointers inward after swap

return nums;Return the rearranged array

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most once by either pointer, so time is linear. No extra space is used beyond variables, so space is constant.

💡 For n=100,000, this means about 100,000 operations and no extra memory, making it efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its in-place partitioning and linear time complexity.

🧠

Two Pointers (Single Pass with Insert Position)

💡 This approach uses a single pointer to track the position to place the next even number, swapping as needed, which is intuitive and efficient.

Intuition

Keep a pointer for the next even position; when an even number is found, swap it with the element at that pointer and move the pointer forward.

Algorithm

1. Initialize an insertPos pointer at 0 to track where the next even number should go.
2. Traverse the array from start to end.
3. When an even number is found, swap it with the element at insertPos and increment insertPos.
4. Continue until the end of the array.
5. Return the modified array.

💡 This method partitions the array in one pass with minimal pointer management, making it less error-prone.

</>

Code

from typing import List

def partitionArrayByParity(nums: List[int]) -> List[int]:
    insertPos = 0
    for i in range(len(nums)):
        if nums[i] % 2 == 0:
            nums[i], nums[insertPos] = nums[insertPos], nums[i]
            insertPos += 1
    return nums

# Driver code
if __name__ == '__main__':
    print(partitionArrayByParity([3,1,2,4]))  # Output: [2,4,3,1] or any valid partition

Line Notes

insertPos = 0Initialize pointer for next even number placement

for i in range(len(nums))Traverse array from start to end

if nums[i] % 2 == 0Check if current number is even

nums[i], nums[insertPos] = nums[insertPos], nums[i]Swap even number forward to insertPos

insertPos += 1Move insertPos forward after placing even number

return numsReturn the partitioned array

import java.util.*;

public class PartitionArrayByParity {
    public static int[] partitionArrayByParity(int[] nums) {
        int insertPos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                int temp = nums[i];
                nums[i] = nums[insertPos];
                nums[insertPos] = temp;
                insertPos++;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] input = {3,1,2,4};
        int[] output = partitionArrayByParity(input);
        System.out.println(Arrays.toString(output)); // Output: [2,4,3,1] or any valid partition
    }
}

Line Notes

int insertPos = 0;Initialize pointer for next even number placement

for (int i = 0; i < nums.length; i++)Traverse array from start to end

if (nums[i] % 2 == 0)Check if current number is even

int temp = nums[i];Store current even number temporarily for swap

nums[i] = nums[insertPos];Move element at insertPos to current position

nums[insertPos] = temp;Place even number at insertPos

insertPos++;Increment insertPos after placing even number

return nums;Return the partitioned array

#include <iostream>
#include <vector>

using namespace std;

vector<int> partitionArrayByParity(vector<int>& nums) {
    int insertPos = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] % 2 == 0) {
            swap(nums[i], nums[insertPos]);
            insertPos++;
        }
    }
    return nums;
}

int main() {
    vector<int> input = {3,1,2,4};
    vector<int> output = partitionArrayByParity(input);
    for (int num : output) cout << num << ' ';
    cout << endl; // Output: 2 4 3 1 or any valid partition
    return 0;
}

Line Notes

int insertPos = 0;Initialize pointer for next even number placement

for (int i = 0; i < (int)nums.size(); i++)Traverse array from start to end

if (nums[i] % 2 == 0)Check if current number is even

swap(nums[i], nums[insertPos]);Swap even number forward to insertPos

insertPos++;Move insertPos forward after placing even number

return nums;Return the partitioned array

function partitionArrayByParity(nums) {
    let insertPos = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 0) {
            [nums[i], nums[insertPos]] = [nums[insertPos], nums[i]];
            insertPos++;
        }
    }
    return nums;
}

// Test
console.log(partitionArrayByParity([3,1,2,4])); // Output: [2,4,3,1] or any valid partition

Line Notes

let insertPos = 0;Initialize pointer for next even number placement

for (let i = 0; i < nums.length; i++)Traverse array from start to end

if (nums[i] % 2 === 0)Check if current number is even

[nums[i], nums[insertPos]] = [nums[insertPos], nums[i]];Swap even number forward to insertPos

insertPos++;Increment insertPos after placing even number

return nums;Return the partitioned array

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space, making it efficient in both time and space.

💡 For n=100,000, this means about 100,000 operations and no extra memory, ideal for interviews.

Interview Verdict: Accepted and optimal

This approach is often preferred for its simplicity and efficiency in coding interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 or 3 is best to code due to optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extra Arrays)	O(n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers (In-Place Partition)	O(n)	O(1)	No	N/A	Preferred approach to code
3. Two Pointers (Single Pass Insert Position)	O(n)	O(1)	No	N/A	Also preferred for simplicity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using extra space.Step 3: Optimize to in-place two pointers approach.Step 4: Optionally present the single-pass insert position method.Step 5: Code the optimal approach and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to recognize partitioning patterns, optimize space, and write clean, bug-free code.

Common Follow-ups

• Can you do this in-place without extra space? → Use two pointers.
• What if order of evens and odds must be preserved? → Use stable partitioning or extra space.

💡 These follow-ups test your understanding of space optimization and stability in partitioning.

🔍

Pattern Recognition

When to Use

1) Need to reorder array by a binary condition; 2) Order within groups does not matter; 3) Want in-place rearrangement; 4) Problem hints at partition or two pointers.

Signature Phrases

reorder array by parityall even integers come before all odd integers

NOT This Pattern When

Sorting the entire array or stable sorting problems are different patterns.

Similar Problems

Sort Colors - partition array into three groupsMove Zeroes - move all zeros to endDutch National Flag - three-way partitioning

Practice

1. You are given an integer array and a target value. The task is to count the number of triplets in the array such that the sum of the triplet is less than the target. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use three nested loops to check all triplets and count those with sum less than target.

B. Sort the array, then for each element use two pointers to find pairs that form triplets with sum less than target.

C. Use dynamic programming to store counts of sums and build up to triplets.

D. Use a greedy approach by always picking the smallest elements first to form triplets.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting triplets with sum less than a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach that reduces complexity

   Sorting and using two pointers allows scanning pairs efficiently for each fixed element, reducing complexity from O(n^3) to O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two pointers is a classic pattern for 3Sum variants [OK]

Hint: Sorting + two pointers reduces triple loops to quadratic [OK]

Common Mistakes:

• Assuming brute force is optimal
• Thinking DP applies directly here
• Believing greedy always works for sum constraints

2. What is the time complexity of the optimal 4Sum solution that uses a hash map to store all pairs of sums and then finds complementary pairs to form quadruplets?

medium

A. O(n^2 + k^2), where k is the average number of pairs per sum stored in the hash map.

B. O(n^4) because all quadruplets are checked explicitly.

C. O(n^3) due to nested loops over pairs and quadruplets.

D. O(n^2 log n) because sorting dominates the complexity.

Solution

1. Step 1: Analyze pair sum generation

   Generating all pairs sums takes O(n^2) time and space.

2. Step 2: Analyze combining pairs to quadruplets

   For each sum, combining pairs from two lists takes O(k^2) where k is average pairs per sum.

3. Step 3: Consider worst case

   In worst case, k can be O(n), so combining pairs can be O(n^2) per sum, leading to O(n^4) overall.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Worst-case complexity is O(n^4), not O(n^2 + k^2) [OK]

Hint: Worst-case complexity can be O(n^4) due to pair combinations [OK]

Common Mistakes:

• Assuming average case complexity applies to worst case
• Ignoring worst-case pair combination cost

3. What is the time and space complexity of the optimal two-pointer overwrite approach for moving zeroes to the end of an array of length n?

medium

A. Time: O(n), Space: O(1) because it scans array twice but no extra space

B. Time: O(n^2), Space: O(1) due to nested loops

C. Time: O(n), Space: O(n) because it uses an auxiliary array implicitly

D. Time: O(n log n), Space: O(1) due to sorting involved

Solution

1. Step 1: Identify loops and operations

   The algorithm scans the array twice sequentially: once to overwrite non-zero elements, once to fill zeroes.

2. Step 2: Analyze time and space

   Each loop is O(n), total O(n). No extra arrays or recursion used, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes, constant extra space [OK]

Hint: Two linear scans, no nested loops or extra arrays [OK]

Common Mistakes:

• Mistaking two loops as nested (O(n^2))
• Assuming extra space due to overwriting
• Confusing with sorting complexity

4. Identify the bug in the following code snippet that attempts to remove duplicates allowing at most two occurrences from a sorted array.

medium

A. Line 5: Incorrectly resetting count only when read_index == 0

B. Line 9: Allowing count <= 2 instead of count < 2

C. Line 6: Not resetting count when element changes

D. Line 3: Initializing count to 0 instead of 1

Solution

1. Step 1: Analyze count initialization

   Count is initialized to 0 before the loop, but since the first element is always counted, it should start at 1 to reflect the first occurrence.

2. Step 2: Impact of incorrect initialization

   Starting count at 0 can cause off-by-one errors in counting duplicates, potentially allowing more than two duplicates or skipping valid ones.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Count should start at 1 to correctly count the first element [OK]

Hint: Initialize count to 1 before loop to count first element [OK]

Common Mistakes:

• Initializing count to 0 causes off-by-one errors
• Not resetting count properly
• Misplaced count increment

5. Examine the following code snippet intended to check if a string is a valid palindrome ignoring case and non-alphanumeric characters. Which line contains a subtle bug that can cause incorrect results on inputs like "A man, a plan, a canal: Panama"?

def isPalindrome(s: str) -> bool:
    cleaned = [ch for ch in s if ch.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left].lower() != cleaned[right].lower():
            return False
        left += 1
        right -= 1
    return True

medium

A. Line 5: if cleaned[left].lower() != cleaned[right].lower(): (case normalization done here)

B. Line 2: cleaned = [ch for ch in s if ch.isalnum()] (missing lowercasing during cleaning)

C. Line 4: while left < right: (correct loop condition)

D. Line 7: right -= 1 (correct pointer decrement)

Solution

1. Step 1: Identify where case normalization occurs

   Case normalization is done inside the loop condition, not during cleaning.

2. Step 2: Understand impact of missing lowercasing in cleaning

   Since cleaned list stores original case, repeated .lower() calls in loop are inefficient but correct; however, this is not a bug causing incorrect results.

3. Step 3: Re-examine line 2

   Line 2 does not lowercase characters, but line 5 does, so no bug here.

4. Step 4: Check for subtle bug

   Actually, no bug in case normalization, but if line 2 did not skip non-alphanumeric characters, that would cause errors. Here, line 2 correctly filters non-alnum.

5. Step 5: Reconsider options

   None of the lines have a bug causing incorrect results on the example input.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Missing lowercasing in cleaning is not a bug since it's done later [OK]

Hint: Case normalization can be done either during cleaning or comparison [OK]

Common Mistakes:

• Not skipping non-alphanumeric characters
• Not normalizing case consistently
• Off-by-one errors in pointer movement