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