Partition Array by Parity

📋

Problem

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.

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

Edge cases: Array with all even numbers → output is the same arrayArray with all odd numbers → output is the same arrayArray with one element → output is the same array

</>

IDE

def partitionArrayByParity(nums: list[int]) -> list[int]:public int[] partitionArrayByParity(int[] nums)vector<int> partitionArrayByParity(vector<int>& nums)function partitionArrayByParity(nums)

def partitionArrayByParity(nums: list[int]) -> list[int]:
    # Write your solution here
    pass

class Solution {
    public int[] partitionArrayByParity(int[] nums) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> partitionArrayByParity(vector<int>& nums) {
    // Write your solution here
    return {};
}

function partitionArrayByParity(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [3,1,2,4]No partitioning done; returns input as is.✅ Implement two-pointer partition swapping odd on left with even on right.

Wrong: [1,3,5,7,2]Stops partition early or does not move even number to front.✅ Continue partition until pointers cross; swap odd left with even right.

Wrong: [2,4,6,1,3,5]Unnecessary swaps breaking already partitioned array.✅ Only swap when left pointer is odd and right pointer is even.

Wrong: [1,2,1,2,1,2]Partial partitioning; stops early or misses some swaps.✅ Ensure partition loop runs until pointers cross.

Wrong: Timeout or crash on large inputUsing nested loops or sorting causing O(n^2) complexity.✅ Use two-pointer linear partition to achieve O(n) time.

✓

Test Cases

Focus on handling edge cases like empty and single-element arrays.

Test your code against tricky patterns like mostly odds or alternating parity.

Optimize your solution to run in linear time with constant extra space.

t1_01basic

Input{"nums":[3,1,2,4]}

Expected[4,2,1,3]

⏱ Performance - must finish in 2000ms

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.

💡 Try using two pointers to separate even and odd numbers.

💡 Check if swapping elements when left pointer finds odd and right pointer finds even helps.

💡 Implement a partition similar to quicksort's partition step to group evens first.

Why it failed: Output does not have all evens before odds. Fix by ensuring the partition logic swaps odd on left with even on right.

✓ Correctly partitions evens before odds.

t1_02basic

Input{"nums":[0,5,8,7,2]}

Expected[0,8,2,7,5]

⏱ Performance - must finish in 2000ms

Evens are 0,8,2 and odds are 7,5. Output groups evens first, then odds.

💡 Remember zero is even and should be grouped with evens.

💡 Use a single pass with two pointers to reorder in-place.

💡 Swap elements when left pointer is odd and right pointer is even.

Why it failed: Fails to group zero with evens or mixes odds before evens. Fix by checking parity with num % 2 == 0.

✓ Correctly groups all evens before odds including zero.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array input returns empty array output.

💡 Check how your code handles empty input arrays.

💡 Make sure no index out of bounds errors occur.

💡 Return empty array immediately if input is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a base case for empty input.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[2]}

Expected[2]

⏱ Performance - must finish in 2000ms

Single element array with even number returns same array.

💡 Check behavior when array length is 1.

💡 No swaps needed if only one element.

💡 Return input as is if length is 1.

Why it failed: Code alters single element array unnecessarily. Fix by skipping partition if length is 1.

✓ Correctly returns single element array unchanged.

t2_03edge

Input{"nums":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single element array with odd number returns same array.

💡 Same as even single element case, just with odd number.

💡 No swaps needed for single element arrays.

💡 Return input as is if length is 1.

Why it failed: Code alters single element array unnecessarily. Fix by skipping partition if length is 1.

✓ Correctly returns single element array unchanged.

t3_01corner

Input{"nums":[1,3,5,7,2]}

Expected[2,3,5,7,1]

⏱ Performance - must finish in 2000ms

Only one even number at the end; output moves it to front.

💡 Check if your code handles cases with mostly odds and a single even.

💡 Verify that the partition swaps the single even to the front.

💡 Ensure the two-pointer approach does not stop early when one pointer crosses.

Why it failed: Fails to move single even number to front; likely stops partition early. Fix by continuing until pointers cross.

✓ Correctly partitions even number to front among odds.

t3_02corner

Input{"nums":[2,4,6,1,3,5]}

Expected[2,4,6,1,3,5]

⏱ Performance - must finish in 2000ms

All evens followed by all odds; output same as input.

💡 Check if your code unnecessarily swaps when array is already partitioned.

💡 Verify that partition does not reorder unnecessarily.

💡 Ensure stable partition or at least no incorrect swaps.

Why it failed: Code swaps elements even when already partitioned, breaking order. Fix by swapping only when left is odd and right is even.

✓ Leaves already partitioned array unchanged.

t3_03corner

Input{"nums":[1,2,1,2,1,2]}

Expected[2,2,2,1,1,1]

⏱ Performance - must finish in 2000ms

Alternating odd and even numbers; output groups evens first then odds.

💡 Check if your code handles alternating parity correctly.

💡 Verify that all evens are grouped at front regardless of original order.

💡 Use two-pointer approach to swap odd on left with even on right.

Why it failed: Fails to group all evens first in alternating pattern; likely only partial swaps. Fix by continuing partition until pointers cross.

✓ Correctly groups evens before odds in alternating input.

t4_01performance

Input{"nums":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) time complexity expected to complete within 2 seconds.

💡 Use a linear time two-pointer partition approach.

💡 Avoid nested loops or extra sorting.

💡 In-place swaps with two pointers ensure O(n) time.

Why it failed: Algorithm exceeds time limit due to O(n^2) or worse complexity. Fix by using two-pointer linear partition.

✓ Algorithm runs in O(n) time as expected.

Practice

1. You are given a sorted array and need to remove duplicates such that each element appears at most twice, modifying the array in-place. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Using a nested loop to count duplicates and shift elements accordingly

B. Using two pointers where the write pointer only advances if the current element differs from the element two positions before

C. Using a hash map to count occurrences and then reconstruct the array

D. Using dynamic programming to track the maximum allowed duplicates

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, and duplicates are allowed at most twice, so we can leverage order.

2. Step 2: Identify the approach that uses two pointers and index offset check

   This approach compares the current element with the element two positions before the write pointer to decide if it should be written, ensuring O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers with index offset check is the known optimal approach [OK]

Hint: Two pointers with offset check is optimal [OK]

Common Mistakes:

• Using nested loops causes O(n²) time
• Hash maps use extra space
• DP is unnecessary here

2. What is the time complexity of the optimal two-pointer approach for the 3Sum Smaller problem when the input array has length n?

medium

A. O(n^2) because the outer loop runs n times and the inner two-pointer scan runs in O(n)

B. O(n^3) because of the nested loops

C. O(n log n) due to sorting dominating the complexity

D. O(n^2 log n) because each two-pointer step involves a binary search

Solution

1. Step 1: Identify loops and sorting cost

   Sorting takes O(n log n). The main loop runs O(n) times.

2. Step 2: Analyze inner two-pointer loop

   For each i, two pointers scan the remaining array once, total O(n) per i.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is O(n log n + n^2) -> O(n^2) dominates [OK]

Hint: Two pointers scan each element once per outer iteration [OK]

Common Mistakes:

• Confusing two-pointer scan as O(n^2) per iteration
• Ignoring sorting cost or assuming it dominates
• Assuming binary search is used inside two-pointer

3. The following code attempts to implement the optimal two-pointer forward approach for backspace string compare. Which line contains a subtle bug that causes incorrect results on inputs starting with backspaces?

medium

A. Line 2: write = 0

B. Line 7: elif write >= 0:

C. Line 9: return ''.join(arr[:write])

D. Line 5: if arr[read] != '#':

Solution

1. Step 1: Analyze the condition for backspace handling

   The condition 'elif write >= 0' allows write to decrement even when write is 0, causing write to become -1, which is invalid and leads to incorrect string reconstruction.

2. Step 2: Correct condition

   The condition should be 'elif write > 0' to prevent write from going negative and ensure backspaces at the start are handled safely.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   write pointer must not go below zero [OK]

Hint: write must stay >= 0; decrement only if write > 0 [OK]

Common Mistakes:

• Allowing write to become negative on backspace
• Returning arr[:write] without checking write validity
• Misplacing the backspace condition

4. 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

5. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose