LeetCode 3467 - Transform Array by Parity

The problem gives us an integer array nums and asks us to transform it using three operations that must be performed in a specific order. First, every even number must be replaced with 0. Second, every odd number must be replaced with 1.

leetcodeeasyarraysortingcounting

LeetCode Problem 3467

Difficulty: 🟢 Easy
Topics: Array, Sorting, Counting

Solution

LeetCode 3467 - Transform Array by Parity

Problem Understanding

The problem gives us an integer array nums and asks us to transform it using three operations that must be performed in a specific order.

First, every even number must be replaced with 0. Second, every odd number must be replaced with 1. After this transformation, the array will contain only zeros and ones. Finally, the transformed array must be sorted in non-decreasing order.

In other words, each original value only contributes its parity information. Even numbers become 0, odd numbers become 1, and then all zeros must appear before all ones in the final result.

For example, if the input is [4,3,2,1], the parity transformation produces [0,1,0,1]. Sorting this array gives [0,0,1,1].

The constraints are very small:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Since the array contains at most 100 elements, almost any reasonable solution will be fast enough. However, it is still useful to identify the simplest and most efficient approach.

Several edge cases are worth considering:

  • An array containing only even numbers should become all zeros.
  • An array containing only odd numbers should become all ones.
  • A single-element array should still be transformed correctly.
  • Duplicate values do not matter because only parity is preserved.
  • The final sorting step means the exact positions of the original elements are irrelevant.

Approaches

Brute Force Approach

The most direct approach follows the problem statement literally.

We iterate through the array and replace each value with either 0 or 1 depending on whether it is even or odd. After the transformation is complete, we sort the array.

This works because it exactly implements the required operations in the required order.

The time complexity is dominated by sorting. Since the transformed array contains n elements, sorting requires O(n log n) time.

Optimal Approach

A key observation is that after the transformation, the array contains only zeros and ones.

Sorting an array of only zeros and ones is equivalent to placing all zeros first and all ones afterward. Therefore, instead of actually sorting, we can simply count how many even numbers and odd numbers exist.

Every even number becomes a zero, and every odd number becomes a one. If there are e even numbers and o odd numbers, then the final sorted array must be:

  • e zeros
  • followed by o ones

This completely avoids the sorting step.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(1) or O(n) depending on sort implementation Transform then sort
Optimal O(n) O(n) Count evens and odds, directly construct result

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a counter for even numbers.
  2. Traverse the array once.
  3. For each number, check whether it is even using num % 2 == 0.
  4. If the number is even, increment the even counter.
  5. After processing all elements, compute the number of odd elements as len(nums) - even_count.
  6. Create the result array consisting of even_count zeros.
  7. Append odd_count ones to the result array.
  8. Return the constructed array.

Why it works

Every even number is transformed into 0, and every odd number is transformed into 1. After sorting, all zeros must appear before all ones. Therefore, the final array is completely determined by the counts of even and odd numbers. Constructing an array with exactly that many zeros followed by that many ones produces the same result as performing the transformation and sorting explicitly.

Python Solution

from typing import List

class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        even_count = 0

        for num in nums:
            if num % 2 == 0:
                even_count += 1

        odd_count = len(nums) - even_count

        return [0] * even_count + [1] * odd_count

The implementation starts by counting how many elements are even. Since every even value eventually becomes 0, this count tells us exactly how many zeros must appear in the final sorted array.

The number of odd elements is simply the total array length minus the number of even elements. Every odd value becomes 1, so this count tells us how many ones are required.

Finally, the result is constructed directly using list multiplication. The expression [0] * even_count creates the required number of zeros, and [1] * odd_count creates the required number of ones. Concatenating them produces the correctly sorted transformed array.

Go Solution

func transformArray(nums []int) []int {
    evenCount := 0

    for _, num := range nums {
        if num%2 == 0 {
            evenCount++
        }
    }

    oddCount := len(nums) - evenCount

    result := make([]int, 0, len(nums))

    for i := 0; i < evenCount; i++ {
        result = append(result, 0)
    }

    for i := 0; i < oddCount; i++ {
        result = append(result, 1)
    }

    return result
}

The Go implementation follows the same logic as the Python solution. It first counts even numbers, computes the number of odd numbers, and then constructs the final slice.

A slice with capacity len(nums) is preallocated to avoid unnecessary reallocations during appends. Integer overflow is not a concern because the maximum array length is only 100.

Worked Examples

Example 1

Input: nums = [4,3,2,1]

Counting Phase

Element Even? evenCount
4 Yes 1
3 No 1
2 Yes 2
1 No 2

After traversal:

  • evenCount = 2
  • oddCount = 4 - 2 = 2

Construction Phase

Step Result
Add 2 zeros [0, 0]
Add 2 ones [0, 0, 1, 1]

Final answer:

[0, 0, 1, 1]

Example 2

Input: nums = [1,5,1,4,2]

Counting Phase

Element Even? evenCount
1 No 0
5 No 0
1 No 0
4 Yes 1
2 Yes 2

After traversal:

  • evenCount = 2
  • oddCount = 5 - 2 = 3

Construction Phase

Step Result
Add 2 zeros [0, 0]
Add 3 ones [0, 0, 1, 1, 1]

Final answer:

[0, 0, 1, 1, 1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to count parity, plus linear result construction
Space O(n) Output array contains n elements

The algorithm performs one traversal of the input array to count even numbers. Constructing the final result also takes linear time because exactly n elements are produced. The returned array itself requires O(n) space, which is unavoidable because the output contains n values.

Test Cases

from typing import List

sol = Solution()

assert sol.transformArray([4, 3, 2, 1]) == [0, 0, 1, 1]  # example 1
assert sol.transformArray([1, 5, 1, 4, 2]) == [0, 0, 1, 1, 1]  # example 2

assert sol.transformArray([2]) == [0]  # single even element
assert sol.transformArray([7]) == [1]  # single odd element

assert sol.transformArray([2, 4, 6, 8]) == [0, 0, 0, 0]  # all even
assert sol.transformArray([1, 3, 5, 7]) == [1, 1, 1, 1]  # all odd

assert sol.transformArray([1, 2]) == [0, 1]  # smallest mixed case
assert sol.transformArray([1000, 999]) == [0, 1]  # boundary values

assert sol.transformArray([8, 6, 4, 2, 1]) == [0, 0, 0, 0, 1]  # many evens
assert sol.transformArray([1, 2, 3, 4, 5, 6]) == [0, 0, 0, 1, 1, 1]  # balanced parity

assert sol.transformArray([10] * 100) == [0] * 100  # maximum length, all even
assert sol.transformArray([11] * 100) == [1] * 100  # maximum length, all odd

Test Summary

Test Why
[4,3,2,1] Validates example 1
[1,5,1,4,2] Validates example 2
[2] Single even element
[7] Single odd element
[2,4,6,8] All elements become zero
[1,3,5,7] All elements become one
[1,2] Smallest mixed parity case
[1000,999] Boundary values for element range
[8,6,4,2,1] Mostly even values
[1,2,3,4,5,6] Equal numbers of evens and odds
[10] * 100 Maximum length, all even
[11] * 100 Maximum length, all odd

Edge Cases

Array Contains Only Even Numbers

An input such as [2, 4, 6, 8] transforms entirely into zeros. A common mistake is to assume both zeros and ones will always appear in the result. The implementation handles this naturally because oddCount becomes zero, producing only zeros.

Array Contains Only Odd Numbers

An input such as [1, 3, 5, 7] transforms entirely into ones. Some implementations may incorrectly rely on sorting transformed values and accidentally mishandle the absence of zeros. The counting approach correctly constructs a result containing only ones.

Single Element Array

When the input length is one, such as [2] or [7], the result must still be valid. The counting logic works without any special handling because the even and odd counts are computed correctly regardless of array size.

Large Number of Duplicate Values

Arrays such as [10, 10, 10, 10] or [11, 11, 11, 11] contain many repeated values. Since the problem only depends on parity, duplicates do not affect correctness. The algorithm counts parity rather than individual values, ensuring duplicates are handled efficiently and correctly.