Sort Array By Parity - Practice Coding Problems

Sort Array By Parity - Problem

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Note: The relative order of even and odd numbers doesn't need to be preserved.

Input & Output

Example 1 — Basic Mixed Array

$ Input: nums = [3,1,2,4]

› Output: [2,4,3,1]

💡 Note: Even numbers 2 and 4 are moved to the beginning, followed by odd numbers 3 and 1. Note: [4,2,1,3] would also be correct.

Example 2 — Single Element

$ Input: nums = [0]

› Output: [0]

💡 Note: Array with single even element remains unchanged.

Example 3 — All Odds Then Evens

$ Input: nums = [1,3,5,2,4,6]

› Output: [2,4,6,1,3,5]

💡 Note: All even numbers [2,4,6] are grouped at the beginning, followed by all odd numbers [1,3,5].

Constraints

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 5000

Visualization

Tap to expand

Understanding the Visualization

Input

Mixed array of even and odd integers

Process

Separate evens and odds (various methods)

Output

Array with all evens first, then all odds

Key Takeaway

🎯 Key Insight: This is a partitioning problem, not a full sorting problem - we only need to separate by parity

Asked in

G Google 15 a Amazon 12 M Microsoft 8 Apple 5

The key insight is to partition the array by parity (even vs odd) rather than fully sorting it. The optimal two-pointers approach achieves this in a single pass with O(n) time and O(1) space by swapping misplaced elements.

Common Approaches

Approach	Time	Space	Notes
✓ Sort with Custom Comparator	O(n log n)	O(1)	Use built-in sort with custom comparator based on parity
Two Pointers In-Place	O(n)	O(1)	Use two pointers to partition array in single pass
Two Pass Collection	O(n)	O(n)	First collect all evens, then collect all odds

Sort with Custom Comparator — Algorithm Steps

Step 1: Create custom comparator that puts evens before odds
Step 2: Apply built-in sort with this comparator

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Original unsorted array

Comparator

Compare based on parity (even < odd)

Sorted

All evens grouped before all odds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int x = *(int*)a;
    int y = *(int*)b;
    return (x % 2) - (y % 2);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    // Sort with custom comparator: even numbers come before odd numbers
    qsort(nums, numsSize, sizeof(int), compare);
    *returnSize = numsSize;
    return nums;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Built-in sort algorithm typically uses O(n log n) comparison-based sorting

⚡ Linearithmic

Space Complexity

O(1)

Most built-in sorts are in-place (except for languages that create new arrays)

✓ Linear Space

180.0K Views

Medium Frequency

~8 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort with Custom Comparator — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler