Sort Array By Parity II - Solution & Explanation
Problem Statement
Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.
Example 1:
Input: nums = [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
Example 2:
Input: nums = [2,3] Output: [2,3]
Constraints:
2 <= nums.length <= 2 * 104nums.lengthis even.- Half of the integers in
numsare even. 0 <= nums[i] <= 1000
Follow Up: Could you solve it in-place?
Approach Overview
Problem Overview: You receive an integer array where half the numbers are even and half are odd. Rearrange the array so that elements at even indices contain even numbers and elements at odd indices contain odd numbers.
Approach 1: Separate Arrays for Even and Odd Numbers (O(n) time, O(n) space)
This approach splits the array into two lists: one storing all even numbers and another storing all odd numbers. After collecting them, iterate through the original array and place values back such that even indices receive values from the even list and odd indices receive values from the odd list. The logic is straightforward and easy to reason about, making it a good starting point when you first see the problem. The trade‑off is extra memory because you store two additional arrays proportional to the input size. This method works well when clarity is more important than space efficiency and introduces the pattern of grouping values before reconstruction, a common technique in array manipulation problems.
Approach 2: Two Pointer Approach (O(n) time, O(1) space)
The optimal solution uses two pointers that jump across indices with the same parity. One pointer starts at index 0 and moves through even positions, while the other starts at index 1 and moves through odd positions. When the even pointer encounters an odd number and the odd pointer encounters an even number, swap them. Each pointer then advances by two positions. Because every element is examined at most once and swaps fix two incorrect placements simultaneously, the algorithm completes in linear time. This in-place technique avoids additional memory and demonstrates a classic two pointers strategy applied to index parity rather than array ends.
The key insight is that incorrect placements always occur in pairs: an odd number sitting in an even index must be matched with an even number sitting in an odd index. Swapping those two elements resolves both violations at once. The algorithm continues until both pointers reach the end of the array.
Although the problem can technically be solved by sorting or repeated searching for the correct parity element, those methods introduce unnecessary overhead compared to the direct pointer approach.
Recommended for interviews: The two pointer solution is what most interviewers expect. It runs in O(n) time and O(1) space while clearly demonstrating control over index traversal and in-place swapping. Mentioning the separate-arrays method first can show initial reasoning, but implementing the pointer-based approach signals stronger algorithmic thinking.
Approach 1: Two Pointer Approach
This approach utilizes two pointers to iteratively place even and odd numbers at the correct indexes.
One pointer is used to find even numbered indexes and the other one for odd numbered indexes. Traverse through the array, and whenever you find an element not in its correct place, swap it with the correct one using the two pointers.
This C implementation uses two pointers; one for indexing even positions and another for odd positions.
Both pointers step through the array stepping by two positions each time, and they swap the odd-even positioned elements whenever they're misplaced.
Complexity
Time Complexity: O(n) since we may visit each element a couple of times.
Space Complexity: O(1) as the swap is done in-place.
Approach 2: Separate Arrays for Even and Odd Numbers
This approach involves segregating even and odd numbers into separate lists and then efficiently assembling them at respected places in the resultant array.
Despite potentially not being in-place, this technique simplifies understanding the array content and meets the problem requirements.
This Python method separates evens and odds into different sublists. Then it assembles those lists alternatively filling into the result array.
This approach straightforwardly constructs a properly sequenced result list.
Code
Python
JavaScript
Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to the auxiliary lists for even and odd numbers.
Approach 3: Two Pointers
We use two pointers i and j to point to even and odd indices, respectively. Initially, i = 0 and j = 1.
When i points to an even index, if nums[i] is odd, we need to find an odd index j such that nums[j] is even, and then swap nums[i] and nums[j]. Continue traversing until i reaches the end of the array.
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 |
|---|---|
| Two Pointer Approach | Time Complexity: O(n) since we may visit each element a couple of times. |
| Separate Arrays for Even and Odd Numbers | Time Complexity: O(n) |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Separate Arrays for Even and Odd Numbers | O(n) | O(n) | When prioritizing clarity or when modifying the original array is not required |
| Two Pointer Approach (In‑Place) | O(n) | O(1) | Best choice for interviews and production due to constant space and simple swaps |
Video Solution
LeetCode Sort Array By Parity II Solution Explained - Java • Nick White • 9,605 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort Array By Parity II easy or hard?
Sort Array By Parity II Python/Java solution
How to solve Sort Array By Parity II in O(n)?
What is the best approach for Sort Array By Parity II?
Is Sort Array By Parity II asked at Google/Amazon/Meta?
What data structure is used in Sort Array By Parity II?
What is the time complexity of Sort Array By Parity II?
Ready to solve this problem?
Practice Sort Array By Parity II with our built-in code editor and test cases.
Practice on FleetCode