922. Sort Array By Parity II
Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 70.7%
Problem Breakdown
The problem requires sorting an array such that all even-indexed positions contain even numbers and all odd-indexed positions contain odd numbers. The input is an array of integers where exactly half are even and the other half are odd. The output should be any permutation of the input array that satisfies the parity condition.
Inputs:
- An array
numsof integers with length between 2 and 20,000. - Each integer in
numsis between 0 and 1000.
Outputs:
- A sorted array where even indices contain even numbers and odd indices contain odd numbers.
Implicit Constraints:
- The array length is always even.
- There are no negative numbers or duplicates that need special handling.
Intuition
A brute-force approach would involve generating all permutations of the array and checking each one to see if it satisfies the parity condition. This is computationally expensive with a time complexity of O(n!) due to the factorial number of permutations.
The key insight is to use a two-pointer technique to swap elements in place, ensuring that we maintain the parity condition as we iterate through the array. This approach leverages the fact that there are exactly half even and half odd numbers, allowing us to efficiently correct any misplaced elements.
Approach
- Initialize two pointers:
even_ptrstarting at 0 (for even indices) andodd_ptrstarting at 1 (for odd indices). - Iterate through the array:
- If the element at
even_ptris odd, swap it with the element atodd_ptr. - Move
odd_ptrto the next odd index.
- If the element at
- Continue this process until both pointers have traversed the entire array.
This approach ensures that all even numbers are placed at even indices and all odd numbers are placed at odd indices in a single pass through the array.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We make a single pass through the array, performing constant-time operations for each element.
- Space Complexity: O(1). The algorithm uses only a fixed amount of extra space (for the two pointers).
Solution
def sortArrayByParityII(nums):
even_ptr = 0
odd_ptr = 1
while even_ptr < len(nums) and odd_ptr < len(nums):
if nums[even_ptr] % 2 != 0:
# Swap the elements at even_ptr and odd_ptr
nums[even_ptr], nums[odd_ptr] = nums[odd_ptr], nums[even_ptr]
# Move odd_ptr to the next odd index
odd_ptr += 2
else:
# Move even_ptr to the next even index
even_ptr += 2
return nums
Edge Cases Handled
- All Even Numbers: The algorithm will correctly place all numbers at even indices since there are no odd numbers to swap.
- All Odd Numbers: Similarly, all numbers will be placed at odd indices.
- Mixed Even and Odd Numbers: The two-pointer technique ensures that misplaced numbers are swapped in a single pass, maintaining the parity condition.