Sort Array By Parity II - Video Solutions
LeetCode Sort Array By Parity II Solution Explained - Java
Sort Array By Parity II - Video Solution
Watch 10 video solutions for Sort Array By Parity II, a easy level problem involving Array, Two Pointers, Sorting. This walkthrough by Nick White has 9,605 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |