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.length is even.nums are even.0 <= nums[i] <= 1000Follow Up: Could you solve it in-place?
In #922 Sort Array By Parity II, the goal is to rearrange the array so that numbers at even indices are even and numbers at odd indices are odd. Since the problem guarantees an equal number of even and odd elements, we can use a two-pointer strategy to place values in their correct positions.
The efficient idea is to maintain two pointers: one that scans even indices (0, 2, 4, ...) and another that scans odd indices (1, 3, 5, ...). When a misplaced element is found at an even index (an odd number), the odd pointer moves forward until it finds an even number placed incorrectly. These two elements can then be swapped to restore the parity rule.
This method avoids unnecessary sorting and processes the array in a single pass. The approach leverages index parity checks using index % 2 and value parity using num % 2. As a result, the algorithm runs efficiently with linear time and minimal extra memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Even/Odd Index Scan) | O(n) | O(1) |
| Sorting + Rearrangement | O(n log n) | O(1) or O(n) |
NeetCodeIO
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.
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.
1#include <stdbool.h>
2void sortArrayByParityII(int* nums, int numsSize) {
3 int even = 0, odd = 1;
4 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.
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.
Time Complexity: O(n)
Space Complexity: O(n) due to the auxiliary lists for even and odd numbers.
1class Solution:
2 def sortArrayByParityII(selfWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of parity or array rearrangement problems often appear in technical interviews, including FAANG-style interviews. They test understanding of array manipulation, pointer techniques, and efficient in-place operations.
The problem can be solved directly using the input array with index pointers, so no additional data structures are required. Simple pointer manipulation and parity checks are enough to rearrange the elements efficiently.
The optimal approach uses a two-pointer technique that scans even and odd indices separately. When a mismatch is found, the elements are swapped to restore the correct parity placement. This allows the array to be fixed in a single linear pass.
Because the problem guarantees equal counts of even and odd numbers, every misplaced element must have a corresponding element to swap with. Two pointers help locate these mismatches quickly without scanning the array multiple times.
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.