# Transform Array by Parity
**Difficulty:** EASY
[External](https://leetcode.com/problems/transform-array-by-parity)
Canonical: https://scaleengineer.com/dsa/problems/transform-array-by-parity
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
You are given an integer array `nums`. Transform `nums` by performing the following operations in the **exact** order specified:

1. Replace each even number with 0.
2. Replace each odd numbers with 1.
3. 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`

# Approaches
## Brute Force: Simulation and Sorting
This approach directly follows the steps outlined in the problem description. First, it iterates through the array, creating a new array where each number is replaced with 0 if it's even and 1 if it's odd. After this transformation, the new array is sorted using a standard sorting algorithm to produce the final result.
**Time:** O(N log N), where N is the number of elements in `nums`. The initial loop to transform the numbers takes O(N) time, but the dominant operation is sorting the array, which typically has a time complexity of O(N log N). · **Space:** O(N), where N is the length of the input array. This is because a new array `result` of size N is created. Some in-place sorting algorithms might reduce this, but creating a new array is a common way to implement this approach.
**Pros:** Very simple to understand and implement as it directly translates the problem statement into code.; Correctly solves the problem according to the specified operations.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than linear-time solutions.; It requires extra space to hold the new array, which can be avoided.
### Explanation
This method is a straightforward implementation of the problem statement. We first create a new array, `result`, of the same length as the input `nums`. We then loop through `nums`, and for each element, we check its parity. If the number is even, we place a 0 in the corresponding position in `result`; if it's odd, we place a 1. This populates the `result` array with 0s and 1s, but not yet in sorted order. The final step is to sort the `result` array in non-decreasing order, which groups all the 0s before the 1s.

```java
import java.util.Arrays;

class Solution {
    public int[] transformArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // Step 1 & 2: Replace even with 0 and odd with 1
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                result[i] = 0;
            } else {
                result[i] = 1;
            }
        }

        // Step 3: Sort the modified array
        Arrays.sort(result);

        return result;
    }
}
```
### Algorithm
1. Create a new integer array `result` of the same size as `nums`.
2. Iterate through the input array `nums` from `i = 0` to `nums.length - 1`.
3. Inside the loop, check if `nums[i]` is even (`nums[i] % 2 == 0`).
   - If it is even, set `result[i] = 0`.
   - Otherwise (if it's odd), set `result[i] = 1`.
4. After the loop finishes, the `result` array will contain a sequence of 0s and 1s in the same order as the parities of the original numbers.
5. Sort the `result` array using a standard library sorting function (e.g., `Arrays.sort()`).
6. Return the sorted `result` array.

## Counting and Rebuilding
This approach recognizes that the final sorted array will simply be a block of 0s followed by a block of 1s. Instead of creating an intermediate unsorted array and then sorting it, we can directly construct the final sorted array. We do this by first counting the number of even numbers, which tells us exactly how many 0s the final array should contain.
**Time:** O(N), where N is the length of the array. We perform two separate, non-nested loops: one to count the even numbers and another to populate the new array. This results in a total time complexity of O(N) + O(N) = O(N). · **Space:** O(N), as a new `result` array of the same size as the input is created to store the final answer.
**Pros:** More efficient than the brute-force approach, with a linear time complexity of O(N).; Avoids the expensive O(N log N) sorting operation.
**Cons:** Requires O(N) extra space for the new result array, which is not optimal.
### Explanation
The key insight here is that sorting an array of 0s and 1s is equivalent to placing all the 0s at the beginning and all the 1s at the end. The number of 0s is equal to the number of even elements in the original array. 

The algorithm first performs a single pass through the input array `nums` to count how many even numbers exist. Once we have this count, say `evenCount`, we know the final array must contain `evenCount` zeros followed by `nums.length - evenCount` ones. We can then create a new array and directly fill it with this structure, completely bypassing the need for a comparison-based sort.

```java
class Solution {
    public int[] transformArray(int[] nums) {
        int n = nums.length;
        int evenCount = 0;

        // Step 1: Count the number of even numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                evenCount++;
            }
        }

        // Step 2: Create and fill the result array directly
        int[] result = new int[n];
        for (int i = 0; i < evenCount; i++) {
            result[i] = 0;
        }
        for (int i = evenCount; i < n; i++) {
            result[i] = 1;
        }

        return result;
    }
}
```
### Algorithm
1. Initialize a counter, `evenCount`, to 0.
2. Iterate through the input array `nums` once.
3. For each number in `nums`, if it is even, increment `evenCount`.
4. After the first pass, `evenCount` will hold the total number of even numbers in the original array.
5. Create a new result array, `result`, of the same size as `nums`.
6. Fill the `result` array: loop from `i = 0` to `evenCount - 1` and set `result[i] = 0`.
7. Loop from `i = evenCount` to `nums.length - 1` and set `result[i] = 1`.
8. Return the `result` array.

## Optimal In-place Counting
This is the most efficient approach, optimizing the counting method to use constant extra space by modifying the input array directly. It operates in two passes. The first pass counts the number of even elements. The second pass overwrites the input array: it fills the beginning of the array with the required number of 0s and the remainder of the array with 1s.
**Time:** O(N). The algorithm involves two passes over the array (one for counting, one for filling), which results in a linear time complexity. · **Space:** O(1). The transformation is done in-place on the input array. No extra space proportional to the input size is used, only a few variables for counting.
**Pros:** Optimal solution with linear time complexity O(N).; Achieves constant space complexity O(1) by performing the transformation in-place.
**Cons:** This approach modifies the original input array. If the caller needs to preserve the original array, a copy must be made beforehand, which would negate the space savings.
### Explanation
This method enhances the counting approach by eliminating the need for a separate result array, thus achieving O(1) space complexity. The logic remains similar: first, determine the final structure of the array by counting. We iterate through `nums` once to find the total count of even numbers, `evenCount`. Then, knowing the final configuration, we re-iterate over the `nums` array itself, overwriting its elements. The first `evenCount` elements are set to 0, and the subsequent elements are set to 1. This avoids allocating new memory and is highly efficient for large inputs.

```java
class Solution {
    public int[] transformArray(int[] nums) {
        int n = nums.length;
        int evenCount = 0;

        // Step 1: Count the number of even numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                evenCount++;
            }
        }

        // Step 2: Overwrite the array in-place
        for (int i = 0; i < evenCount; i++) {
            nums[i] = 0;
        }
        for (int i = evenCount; i < n; i++) {
            nums[i] = 1;
        }

        return nums;
    }
}
```
### Algorithm
1. Initialize a counter, `evenCount`, to 0.
2. Iterate through the input array `nums` to count the number of even elements, incrementing `evenCount` for each one found.
3. After counting, the value of `evenCount` tells us that the first `evenCount` elements of the final array should be 0.
4. Perform a second pass over the `nums` array to modify it in-place.
5. Loop from index `i = 0` to `evenCount - 1` and set `nums[i] = 0`.
6. Loop from index `i = evenCount` to `nums.length - 1` and set `nums[i] = 1`.
7. Return the modified `nums` array.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 nums

```