Transform Array by Parity
EasyPrompt
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
numsin 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
numsin non-descending order,nums = [0, 0, 1, 1, 1].
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
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
resultof the same size asnums. - Iterate through the input array
numsfromi = 0tonums.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.
- If it is even, set
- After the loop finishes, the
resultarray will contain a sequence of 0s and 1s in the same order as the parities of the original numbers. - Sort the
resultarray using a standard library sorting function (e.g.,Arrays.sort()). - Return the sorted
resultarray.
Walkthrough
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
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.
Trade-offs
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.
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.
Algorithm
- Initialize a counter,
evenCount, to 0. - Iterate through the input array
numsonce. - For each number in
nums, if it is even, incrementevenCount. - After the first pass,
evenCountwill hold the total number of even numbers in the original array. - Create a new result array,
result, of the same size asnums. - Fill the
resultarray: loop fromi = 0toevenCount - 1and setresult[i] = 0. - Loop from
i = evenCounttonums.length - 1and setresult[i] = 1. - Return the
resultarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a counter,
evenCount, to 0. - Iterate through the input array
numsto count the number of even elements, incrementingevenCountfor each one found. - After counting, the value of
evenCounttells us that the firstevenCountelements of the final array should be 0. - Perform a second pass over the
numsarray to modify it in-place. - Loop from index
i = 0toevenCount - 1and setnums[i] = 0. - Loop from index
i = evenCounttonums.length - 1and setnums[i] = 1. - Return the modified
numsarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 numsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.