Sort Array By Parity - Solution & Explanation
Problem Statement
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.
Example 1:
Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Example 2:
Input: nums = [0] Output: [0]
Constraints:
1 <= nums.length <= 50000 <= nums[i] <= 5000
Approach Overview
Problem Overview: You receive an integer array and must reorder it so that all even numbers appear before all odd numbers. The relative order does not matter. Any valid arrangement where every even value comes before every odd value is accepted.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach treats the array like a partitioning problem. Use two pointers: one starting from the left and one from the right. The left pointer searches for an odd number that is misplaced, while the right pointer searches for an even number that should move forward. When both conditions are met, swap the elements and move both pointers inward. Each element is inspected at most once, which keeps the runtime linear. This in-place strategy is memory efficient and mirrors the partition logic used in quicksort-style problems. It is a common pattern when working with two pointers on an array.
The key insight is that you do not need full sorting. The task only requires grouping elements by parity. By continuously correcting misplaced elements from both ends, the array gradually forms two partitions: evens on the left and odds on the right. Because swaps occur directly inside the original array, no extra memory is required.
Approach 2: Separate and Concatenate (O(n) time, O(n) space)
This method builds two temporary lists while iterating through the array once. During the iteration, check each element with num % 2. Append even numbers to one list and odd numbers to another. After the pass completes, concatenate the even list with the odd list to produce the final result. The logic is straightforward and easy to implement, making it a good baseline solution when clarity matters more than memory usage.
The tradeoff is extra space. Since two auxiliary lists are created, the space complexity grows linearly with the input size. However, the runtime remains O(n) because each element is processed once. Conceptually, this approach resembles a simplified grouping step often used before sorting or partitioning operations.
Recommended for interviews: The two-pointer technique is the solution most interviewers expect. It demonstrates that you recognize this as a partition problem and can solve it in-place with O(n) time and O(1) space. The separate-and-concatenate approach still shows correct reasoning and linear processing, but the additional memory makes it less optimal.
Approach 1: Approach 1: Two-Pointer Technique
The two-pointer technique is useful to place even numbers at the beginning and odd numbers at the end in an in-place manner. We start with two pointers, one at the beginning and the other at the end of the array. If the element at the start is even, move the start pointer forward. If the element at the end is odd, move the end pointer backward. Whenever we find an odd number at the start pointer and an even number at the end pointer, we swap them. Continue this process until the two pointers meet.
This C implementation uses two indexes to rearrange the list in place by swapping elements when needed.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since no additional data structures are used.
Approach 2: Approach 2: Separate and Concatenate
This approach involves creating two separate lists: one for even numbers and one for odd numbers. We traverse the original array and append every even number to the even list and every odd number to the odd list. Finally, concatenate the even list with the odd list to form the result.
This solution in C separates even and odd numbers into different positions on a new array.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers
We use two pointers i and j to point to the beginning and end of the array respectively. When i < j, we perform the following operations.
- If
nums[i]is even, then incrementiby1. - If
nums[j]is odd, then decrementjby1. - If
nums[i]is odd andnums[j]is even, then swapnums[i]andnums[j]. Then incrementiby1, and decrementjby1.
Finally, return the array nums.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Separate and Concatenate | Time Complexity: O(n) |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best general solution when in-place modification is allowed and minimal memory usage is preferred. |
| Separate and Concatenate | O(n) | O(n) | Good for readability or functional-style implementations where creating new arrays is acceptable. |
Video Solution
Sort Array by Parity - Leetcode 905 - Python • NeetCodeIO • 11,694 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort Array By Parity easy or hard?
Sort Array By Parity Python/Java solution
How to solve Sort Array By Parity in O(n)?
What is the best approach for Sort Array By Parity?
Is Sort Array By Parity asked at Google/Amazon/Meta?
What data structure is used in Sort Array By Parity?
What is the time complexity of Sort Array By Parity?
Ready to solve this problem?
Practice Sort Array By Parity with our built-in code editor and test cases.
Practice on FleetCode