Transform Array by Parity solution and explanation
Infosys
9 more videos on this problem
Leetcode | 3467. Transform Array by Parity | Easy | Java SolutionDeveloper Docs · 3:58 · 705 views
LeetCode 3467 | Transform Array by Parity 🔄 | Java + Python 💻 | Easy Explanation | Placement Seri...Logic Over Syntax · 17:28 · 319 views
3467. Transform Array by Parity | Biweekly Contest 151 | Arrays | Brute | Optimal | LeetcodeRapid Syntax · 6:41 · 281 views
LeetCode 3467 | Transform Array by Parity 🔄⚖️ | Array Problem ExplanationLogic Over Syntax · 9:57 · 187 views
3467. Transform Array by Parity (Leetcode Easy)Programming Live with Larry · 3:12 · 179 views
Biweekly Contest 151 | First 3 Problems - 3467, 3468 & 3469 | LeetcodeAmit Choraria · 27:34 · 120 views
LeetCode 3467 | Transform Array By Parity | Easy Java SolutionGurugu Rakesh · 7:48 · 104 views
LeetCode 3467: Transform Array by Parity | C# Solution | Two Pointer ApproachCode Scribbler · 5:33 · 67 views
Leetcode 3467 Transform Array by ParityAlgorithmicIQ · 9:04 · 21 views
LeetCode 3467 | Transform Array by Parity Explained Step by Step (C++)Tulya Jain · 3:30 · 5 views
The problem
You are given an integer array nums. Transform nums by performing the following operations in the exact order specified:
- Replace each even number with 0.
- Replace each odd numbers with 1.
- Sort the modified array in non-decreasing order.
Return the resulting array after performing these operations.
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
numsin 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
numsin non-descending order,nums = [0, 0, 1, 1, 1].
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1000
Approach overview
Problem Overview: You are given an integer array and need to transform it so that elements are grouped by parity. All even numbers should appear before odd numbers in the final array. The relative order usually does not matter, so the goal is simply to separate values based on whether num % 2 == 0.
Approach 1: Sorting by Parity (O(n log n) time, O(1) space)
A straightforward way is to sort the array using a custom comparator that prioritizes even numbers over odd numbers. Most languages allow sorting with a key such as num % 2, which naturally places even values first. This works because even numbers evaluate to 0 and odd numbers to 1. The approach relies on standard sorting algorithms, which typically run in O(n log n) time and use constant or logarithmic extra space depending on implementation. It is simple but slower than necessary for this problem.
Approach 2: Two-Pointer Partition (O(n) time, O(1) space)
You can treat the array like a partition problem. Maintain two pointers: one from the start and one from the end. Move the left pointer forward while it points to even numbers, and move the right pointer backward while it points to odd numbers. When an odd number appears on the left and an even number on the right, swap them. This approach processes each element at most once, making it linear time. The idea is similar to partitioning used in quicksort and works well for problems involving arrays and in-place rearrangement.
Approach 3: Counting Evens and Odds (O(n) time, O(1) extra space)
The counting strategy is the simplest when you only need the final parity grouping. First iterate through the array and count how many elements are even. Then overwrite the array: fill the first evenCount positions with even numbers and the remaining positions with odd numbers while scanning the original data. This approach relies on a simple counting technique and sequential iteration. Because it performs two linear passes and only stores a few counters, it runs in O(n) time with constant space.
Recommended for interviews: The two-pointer or counting approach is what interviewers expect. Sorting shows you understand the requirement but wastes time complexity. Demonstrating an O(n) partition or counting solution shows stronger control over array traversal and in-place transformations.
Solution
We can traverse the array nums and count the number of even elements even. Then, we set the first even elements of the array to 0 and the remaining elements to 1.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
class Solution:
def transformArray(self, nums: List[int]) -> List[int]:
even = sum(x % 2 == 0 for x in nums)
for i in range(even):
nums[i] = 0
for i in range(even, len(nums)):
nums[i] = 1
return numsclass Solution {
public int[] transformArray(int[] nums) {
int even = 0;
for (int x : nums) {
even += (x & 1 ^ 1);
}
for (int i = 0; i < even; ++i) {
nums[i] = 0;
}
for (int i = even; i < nums.length; ++i) {
nums[i] = 1;
}
return nums;
}
}class Solution {
public:
vector<int> transformArray(vector<int>& nums) {
int even = 0;
for (int x : nums) {
even += (x & 1 ^ 1);
}
for (int i = 0; i < even; ++i) {
nums[i] = 0;
}
for (int i = even; i < nums.size(); ++i) {
nums[i] = 1;
}
return nums;
}
};function transformArray(nums: number[]): number[] {
const even = nums.filter(x => x % 2 === 0).length;
for (let i = 0; i < even; ++i) {
nums[i] = 0;
}
for (let i = even; i < nums.length; ++i) {
nums[i] = 1;
}
return nums;
}func transformArray(nums []int) []int {
even := 0
for _, x := range nums {
even += x&1 ^ 1
}
for i := 0; i < even; i++ {
nums[i] = 0
}
for i := even; i < len(nums); i++ {
nums[i] = 1
}
return nums
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting by parity | O(n log n) | O(1) | Quick implementation when performance is not critical |
| Two-pointer partition | O(n) | O(1) | Best in-place method when order does not matter |
| Counting evens and odds | O(n) | O(1) | Simplest logic when you just need grouped parity |
Frequently asked questions
Is Transform Array by Parity easy or hard?
Transform Array by Parity is considered an Easy problem because it mainly tests basic array traversal and parity checking using num % 2. The main challenge is recognizing that sorting is unnecessary and a linear-time partition approach is better.
Transform Array by Parity Python/Java solution
Most implementations iterate through the array and either swap elements with two pointers or count even numbers first and rebuild the array. The logic is identical across Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Transform Array by Parity in O(n)?
Traverse the array with two pointers. Move the left pointer until you find an odd number and the right pointer until you find an even number, then swap them. Continue until the pointers meet, ensuring all even values appear before odd values in linear time.
What is the best approach for Transform Array by Parity?
The optimal approach runs in O(n) time using either a two-pointer partition or a counting strategy. Both scan the array once and rearrange elements so all even numbers appear before odd numbers. These methods avoid the unnecessary O(n log n) cost of sorting.
Is Transform Array by Parity asked at Google/Amazon/Meta?
Parity partitioning problems frequently appear in interviews at companies like Amazon and Google because they test array manipulation and in-place partitioning techniques. Variations of this problem are commonly used to evaluate pointer logic and time complexity awareness.
What data structure is used in Transform Array by Parity?
The problem primarily uses arrays and basic iteration. Efficient solutions rely on techniques like two-pointer traversal or simple counting without requiring additional data structures.
What is the time complexity of Transform Array by Parity?
The optimal solution runs in O(n) time because each element is processed at most once. Space complexity is O(1) since the rearrangement can be done in place using pointers or simple counters.