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] <= 1000
Follow Up: Could you solve it in-place?
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.
C++
Java
Python
C#
JavaScript
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.
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.
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) due to the auxiliary lists for even and odd numbers.
| 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) |
Sort Array by Parity - Leetcode 905 - Python • NeetCodeIO • 9,990 views views
Watch 9 more video solutions →Practice Sort Array By Parity II with our built-in code editor and test cases.
Practice on FleetCode