The Sort Array By Parity problem on Leetcode is an engaging array manipulation problem that tests a programmer’s ability to efficiently reorganize elements based on specific criteria. In this comprehensive article, we’ll dissect the problem statement, explore various solution strategies, discuss Python implementations, and finally, delve into the time and space complexities of the proposed solutions.
Table of Contents:
- Understanding the Problem Statement
- Initial Approach: Two-pass Solution
- Two-pointer Approach
- In-place Reordering
- Python Implementations
- Complexity Analysis
1. Understanding the Problem Statement
Given an array
A of non-negative integers, return an array consisting of all the even elements of
A, followed by all the odd elements of
You may return any answer array that satisfies the problem’s conditions.
Input: [3,1,2,4] Output: [2,4,3,1]
[4,2,1,3] would also be accepted.
2. Initial Approach: Two-pass Solution
One of the most straightforward solutions is to iterate through the array twice. During the first iteration, collect all even numbers, and in the second iteration, collect all odd numbers.
- Initialize two lists:
- Iterate through the array, adding even numbers to
evensand odd numbers to
- Merge the lists and return.
3. Two-pointer Approach
Another technique is to use two pointers, one starting at the beginning of the array and the other at the end. Repeatedly swap numbers until the two pointers meet.
- Initialize two pointers:
leftat 0 and
rightat the last index.
- If the number at
leftis even, increment
- If the number at
rightis odd, decrement
- Otherwise, swap the numbers at
4. In-place Reordering
A variant of the two-pointer approach is to do in-place reordering without swapping.
- Iterate through the array with a pointer
i, placing even numbers at the beginning.
- Use another pointer
jto keep track of the position where even numbers should be placed.
5. Python Implementations
def sortArrayByParity(A): evens = [x for x in A if x % 2 == 0] odds = [x for x in A if x % 2 == 1] return evens + odds
def sortArrayByParity(A): left, right = 0, len(A) - 1 while left < right: if A[left] % 2 > A[right] % 2: A[left], A[right] = A[right], A[left] if A[left] % 2 == 0: left += 1 if A[right] % 2 == 1: right -= 1 return A
def sortArrayByParity(A): j = 0 for i in range(len(A)): if A[i] % 2 == 0: A[i], A[j] = A[j], A[i] j += 1 return A
6. Complexity Analysis
Time Complexity: O(n) – We iterate over the array twice.
Space Complexity: O(n) – We create two additional lists to store even and odd numbers.
Time Complexity: O(n) – In the worst case, we might have to look at each element.
Space Complexity: O(1) – We do the sorting in-place without using extra space.
Time Complexity: O(n) – We go through the array once.
Space Complexity: O(1) – No extra space other than the input array is used.
The Sort Array By Parity problem on Leetcode offers multiple angles of attack. While the initial two-pass solution is intuitive and straightforward, the two-pointer and in-place reordering techniques are more space-efficient and elegant.