#3467

Easy

LeetCode Problem Workspace

Transform Array by Parity

Transform an array by sorting even numbers first, followed by odd numbers.

Problem Statement

You are given an integer array nums. Transform nums by placing all the even numbers first, followed by all the odd numbers. The relative order of even and odd numbers should be preserved. Return the resulting array after performing this operation.

For example, given nums = [4,3,2,1], the output should be [0,0,1,1], where even numbers (0) are placed before odd numbers (1).

Examples

Example 1

Input: nums = [4,3,2,1]

Output: [0,0,1,1]

Example 2

Input: nums = [1,5,1,4,2]

Output: [0,0,1,1,1]

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 1000

Solution Approach

Sorting Approach

Sort the array with a custom comparator that prioritizes even numbers before odd ones. While this method is straightforward, the time complexity is dependent on the sorting algorithm used.

Counting and Rebuilding Approach

Count the number of even and odd numbers in the array, then rebuild the array by first placing all even numbers followed by the odd numbers. This can be achieved in linear time after the counting phase.

In-place Partitioning

Use a two-pointer technique to partition the array in-place, moving all even numbers to the front and odd numbers to the back without needing extra space.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of sorting-based approaches is O(n log n), while counting and rebuilding or in-place partitioning methods achieve O(n) time complexity. Space complexity varies from O(n) in the case of sorting to O(1) for in-place solutions.

What Interviewers Usually Probe

Candidate understands sorting and partitioning techniques.
Candidate demonstrates knowledge of array manipulation and space efficiency.
Candidate is able to explain the impact of different approaches on time complexity.

Common Pitfalls or Variants

Common pitfalls

Confusing the order of even and odd numbers during implementation.
Forgetting to maintain the relative order of even and odd numbers.
Relying on inefficient sorting techniques when a linear time solution is possible.

Follow-up variants

Change the constraints to allow for larger array sizes.
Add constraints on the range of values for nums.
Require that the array be sorted in descending order after partitioning.

FAQ

What is the main strategy behind the "Transform Array by Parity" problem?

The main strategy is to sort the array such that all even numbers appear before the odd numbers while maintaining their relative order.

How can I solve this problem with minimal space?

You can solve this problem in-place using a two-pointer technique to partition the array without extra space.

Is there a more efficient approach than sorting?

Yes, counting the even and odd numbers and then reconstructing the array can achieve linear time complexity, which is more efficient than sorting.

What is the time complexity of the sorting solution?

The time complexity of the sorting-based solution is O(n log n), where n is the size of the array.

How does GhostInterview help in solving this problem?

GhostInterview guides you through multiple approaches, helps avoid common mistakes, and prepares you for the interviewer's signals on array manipulation problems.

terminal

Solution

Solution 1: Counting

We can traverse the array $\textit{nums}$ and count the number of even elements $\textit{even}$. Then, we set the first $\textit{even}$ elements of the array to $0$ and the remaining elements to $1$.

1

2

3

4

5

6

7

8

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

Continue Practicing

#3267 count almost equal pairs ii #3265 count almost equal pairs i #3186 maximum total damage with spell casting