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.

Description Hints 1 Solution Video 3:58

3467. Transform Array by Parity

Easy89.7% acceptance1 company

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 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

Asked at 1 company

Infosys

Topics

Hints open one at a time

Hint 1

Let x be the number of even numbers, and y be the number of odd numbers. Output 0 x times, followed by 1 y times.

3:58

Still stuck?Read the written solution, or watch a walkthrough.

Open solution