905. Sort Array By Parity
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 75.0%
Problem Breakdown
The problem requires sorting an array such that all even numbers come before any odd numbers. The input is a non-empty array of non-negative integers. The output should be any permutation of the input array where even numbers precede odd numbers. There are no implicit constraints regarding duplicates or negative numbers since the problem specifies non-negative integers.
Intuition
A brute-force approach would involve iterating through the array twice: once to collect all even numbers and another to collect all odd numbers, then concatenating these two lists. This approach is straightforward but inefficient with a time complexity of O(n) for collecting elements and O(n) for concatenation, resulting in an overall time complexity of O(2n), which simplifies to O(n). However, it uses additional space proportional to the size of the input array.
A more efficient approach involves using two pointers or indices to partition the array in a single pass. The key insight is that we can maintain two pointers: one starting at the beginning of the array (for placing even numbers) and another starting just after the end of the array (for placing odd numbers). As we iterate through the array, we swap elements to ensure all even numbers are moved to the front and all odd numbers are moved to the back.
Approach
We will use a two-pointer technique to partition the array:
- Initialize two pointers:
leftat the start of the array andrightjust after the end of the array. - Iterate through the array with a pointer
i. - If the element at
A[i]is even, increment bothleftandi. - If the element at
A[i]is odd, swap it with the element atright, then decrementright. - Continue this process until
isurpassesright.
This approach ensures that all even numbers are moved to the front of the array and all odd numbers are moved to the back in a single pass.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
- Space Complexity: O(1). The algorithm uses only a constant amount of extra space for the pointers and does not require additional data structures.
Solution
def sortArrayByParity(A):
left, right = 0, len(A) - 1
while left <= right:
if A[left] % 2 == 0:
left += 1
else:
A[left], A[right] = A[right], A[left]
right -= 1
return A
Edge Cases Handled
- All Even Numbers: If the array contains only even numbers, the
leftpointer will traverse the entire array without any swaps. - All Odd Numbers: If the array contains only odd numbers, the
rightpointer will traverse the entire array without any swaps. - Single Element Array: The algorithm handles arrays with a single element correctly by not performing any swaps.
- Empty Array: Although the problem specifies that the input array is non-empty, if we were to extend this solution to handle an empty array, it would naturally return an empty array without any modifications.