3467. Transform Array by Parity

Problem Description

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 number with 1.
Sort the modified array in non-decreasing order.

Return the resulting array after performing these operations.

Intuition

The goal is to modify the array nums such that all even numbers are turned into 0s and all odd numbers are converted to 1s, followed by sorting the resulting array in non-decreasing order.

The intuition behind this solution is straightforward:

Counting Even Numbers: First, determine how many numbers in the array nums are even. This count will dictate how many 0s should be at the beginning of the transformed array since, in the sorted order, 0s should precede 1s.
Construct the Transformed Array: By using the count of even numbers, replace the first even number of elements in the array with 0s. The remainder of the array should be filled with 1s.

This approach takes advantage of the fact that knowing the count of even numbers allows us to easily set up the final sorted order of the modified array. By separating the modification of each integer into counting and then assigning values based on this count, the problem is simplified into a linear process over the array.

Learn more about Sorting patterns.

Solution Approach

The solution approach involves a straightforward algorithm that encompasses counting, modifying, and assigning values within the array nums. Here's how it is implemented:

Count Even Numbers:
- Traverse the array nums and use a generator expression to count how many numbers are even. This is achieved with the expression sum(x % 2 == 0 for x in nums). The expression evaluates to True (or 1) for even numbers and False (or 0) for odd numbers, and the sum() function totals these values to give the count of even numbers, stored in even.
Transform the Array:
- After determining the number of even numbers, the array nums is transformed accordingly:
  - The elements from index 0 to even are assigned the value 0 by iterating from 0 to even. This fills the initial portion of the array with zeros.
  - The remaining elements, from index even to the end of the array, are then filled with 1. Thus, iterating from even to len(nums) allows for straightforward assignment.

By following this algorithm, the modified array is inherently sorted as the problem specifies replacement of even numbers with zeros and odd numbers with ones. This leads directly to the required non-decreasing sorted order by nature of binary values.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the integer array nums = [3, 2, 4, 5]. Let's walk through the solution step-by-step:

Step 1: Count Even Numbers

Traverse nums to calculate the number of even numbers:
- For 3, 3 % 2 != 0 (odd), contributes 0.
- For 2, 2 % 2 == 0 (even), contributes 1.
- For 4, 4 % 2 == 0 (even), contributes 1.
- For 5, 5 % 2 != 0 (odd), contributes 0.
Using the generator expression sum(x % 2 == 0 for x in nums), the count of even numbers is 2.

Step 2: Transform and Sort the Array

Initialize the array with zeros from index 0 to even (2):
- At index 0, set value to 0.
- At index 1, set value to 0.
Initialize ones from even to len(nums):
- At index 2, set value to 1.
- At index 3, set value to 1.

The resulting array after transformation and sorting is [0, 0, 1, 1].

Thus, by counting and transforming the elements in the specified manner, we achieve the desired non-decreasing sorted array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def transformArray(self, nums: List[int]) -> List[int]:
5        # Calculate the count of even numbers in the list 'nums'
6        even_count = sum(x % 2 == 0 for x in nums)
7      
8        # Set the first 'even_count' elements of 'nums' to 0
9        for i in range(even_count):
10            nums[i] = 0
11      
12        # Set the remaining elements of 'nums' to 1
13        for i in range(even_count, len(nums)):
14            nums[i] = 1
15      
16        return nums
17

1class Solution {
2    public int[] transformArray(int[] nums) {
3        int evenCount = 0; // Initialize a counter for even numbers
4
5        // Iterate through the array to count how many numbers are even
6        for (int number : nums) {
7            evenCount += (number & 1 ^ 1); // Increment if the number is even
8        }
9
10        // Set the first 'evenCount' positions to 0
11        for (int i = 0; i < evenCount; ++i) {
12            nums[i] = 0;
13        }
14
15        // Set the remaining positions to 1
16        for (int i = evenCount; i < nums.length; ++i) {
17            nums[i] = 1;
18        }
19      
20        return nums; // Return the transformed array
21    }
22}
23

1#include <vector>
2
3class Solution {
4public:
5    // Method to transform the array so that all even numbers come first, followed by odd numbers.
6    std::vector<int> transformArray(std::vector<int>& nums) {
7        int evenCount = 0; // Initialize a counter for even numbers
8      
9        // Iterate over each number in the array
10        for (int num : nums) {
11            // Check if the number is even
12            evenCount += !(num & 1); // Increment even count if num is even
13        }
14      
15        // Set the first 'evenCount' elements to 0 (representing even numbers)
16        for (int i = 0; i < evenCount; ++i) {
17            nums[i] = 0;
18        }
19      
20        // Set the remaining elements to 1 (representing odd numbers)
21        for (int i = evenCount; i < nums.size(); ++i) {
22            nums[i] = 1;
23        }
24      
25        return nums; // Return the transformed array
26    }
27};
28

1// Function to transform an array by setting the first 'even' numbers to 0 and the rest to 1
2function transformArray(nums: number[]): number[] {
3    // Count how many numbers in the array are even
4    const evenCount = nums.filter(num => num % 2 === 0).length;
5
6    // Set the first 'evenCount' elements in the array to 0
7    for (let i = 0; i < evenCount; ++i) {
8        nums[i] = 0;
9    }
10
11    // Set the remaining elements in the array to 1
12    for (let i = evenCount; i < nums.length; ++i) {
13        nums[i] = 1;
14    }
15
16    // Return the transformed array
17    return nums;
18}
19

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This complexity arises because the algorithm involves iterating through the array twice: once to count even numbers and once more to transform the array.

The space complexity of the code is O(1). The transformation is done in-place, meaning no additional space proportional to the size of the input array is used, other than a few variables for counting.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know