Transform Array by Parity

EASY

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

Approaches

Checkout 3 different approaches to solve Transform Array by Parity. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Create a new integer array result of the same size as nums.
Iterate through the input array nums from i = 0 to nums.length - 1.
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.
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.
Sort the result array using a standard library sorting function (e.g., Arrays.sort()).
Return the sorted result array.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Transform Array by Parity. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Transform Array by Parity

Algorithms:

Sorting

Patterns:

Counting

Data Structures:

Array

Companies:

Infosys |