Difficulty: Easy | Acceptance: 89.80% | Paid: No Topics: Array, Sorting, Counting
You are given an array of integers nums. Transform the array such that all even integers appear before all odd integers. The relative order of even numbers among themselves and odd numbers among themselves should be preserved.
Return the transformed array.
- Examples
- Constraints
- Two-Pass Approach
- Two-Pointer In-Place Approach
- Sorting Approach
Examples
Example 1
Input:
nums = [4,3,2,1]
Output:
[0,0,1,1]
Explanation: Replace the even numbers (4 and 2) with 0 and the odd numbers (3 and 1) with 1. Now, nums = [0, 1, 0, 1].
After sorting nums in non-descending order, nums = [0, 0, 1, 1].
Example 2
Input:
nums = [1,5,1,4,2]
Output:
[0,0,1,1,1]
Explanation: Replace the even numbers (4 and 2) with 0 and the odd numbers (1, 5 and 1) with 1. Now, nums = [1, 1, 1, 0, 0].
After sorting nums in non-descending order, nums = [0, 0, 1, 1, 1].
Constraints
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 1000
Two-Pass Approach
Intuition Make two passes through the array: first collect all even numbers, then collect all odd numbers. This naturally preserves the relative order within each group.
Steps
- Create an empty result array
- First pass: iterate through nums and add all even numbers to result
- Second pass: iterate through nums and add all odd numbers to result
- Return the result array
from typing import List
class Solution:
def transformArray(self, nums: List[int]) -> List[int]:
result = []
for num in nums:
if num % 2 == 0:
result.append(num)
for num in nums:
if num % 2 == 1:
result.append(num)
return result
Complexity
- Time: O(n) where n is the length of the array
- Space: O(n) for the result array
- Notes: Preserves relative order but uses extra space
Two-Pointer In-Place Approach
Intuition Use two pointers from both ends of the array. The left pointer finds odd numbers, and the right pointer finds even numbers. Swap them when both are found.
Steps
- Initialize left pointer at 0 and right pointer at n-1
- While left < right:
- Move left pointer right while nums[left] is even
- Move right pointer left while nums[right] is odd
- If left < right, swap nums[left] and nums[right]
- Return the array
from typing import List
class Solution:
def transformArray(self, nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
while left < right and nums[left] % 2 == 0:
left += 1
while left < right and nums[right] % 2 == 1:
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
Complexity
- Time: O(n) where n is the length of the array
- Space: O(1) in-place modification
- Notes: Does not preserve relative order but uses constant space
Sorting Approach
Intuition Sort the array using a custom comparator where even numbers are considered “smaller” than odd numbers.
Steps
- Sort the array with a comparator that returns true for (even, odd) pairs
- Return the sorted array
from typing import List
class Solution:
def transformArray(self, nums: List[int]) -> List[int]:
nums.sort(key=lambda x: x % 2)
return nums
Complexity
- Time: O(n log n) due to sorting
- Space: O(1) or O(n) depending on the sorting algorithm
- Notes: Simple to implement but slower than linear approaches