#922

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Sort Array By Parity II

Sort an array where even numbers appear at even indices and odd numbers appear at odd indices using two-pointer scanning.

array two pointers sorting

Problem Statement

Given an array nums with an even length, the array contains an equal number of even and odd integers. Your task is to rearrange the array such that all even numbers are positioned at even indices and all odd numbers are positioned at odd indices. The order of the numbers does not need to be maintained, but the positions should adhere to the parity rule.

For example, if nums = [4, 2, 5, 7], the correct output could be [4, 5, 2, 7] or any permutation that satisfies the parity condition. Your task is to implement an efficient solution with a focus on maintaining time and space complexity constraints.

Examples

Example 1

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

Output: [4,5,2,7]

[4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2

Input: nums = [2,3]

Output: [2,3]

Example details omitted.

Constraints

2 <= nums.length <= 2 * 104
nums.length is even.
Half of the integers in nums are even.
0 <= nums[i] <= 1000

Solution Approach

Two-pointer scanning

The problem can be solved by using two pointers: one pointing to the next even index and the other to the next odd index. You then scan the array and swap the numbers as needed, ensuring the parity condition is satisfied at every step. This technique minimizes unnecessary operations and ensures an optimal time complexity.

In-place swaps

By using the two-pointer approach, the array can be sorted in-place, meaning no extra space is needed aside from the input array itself. This optimizes space complexity while maintaining an O(n) time complexity.

Invariant tracking

During the two-pointer scan, track the invariant where even-indexed positions must hold even numbers and odd-indexed positions must hold odd numbers. This invariant is key to ensuring the solution is correct and efficient.

Complexity Analysis

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

The time complexity is O(n) because each element is processed exactly once during the two-pointer scan. The space complexity is O(1) since no additional data structures are used apart from the input array.

What Interviewers Usually Probe

Look for a candidate's understanding of two-pointer techniques and their ability to maintain invariant conditions during an array traversal.
Evaluate the candidate's familiarity with array manipulation and in-place swapping as an optimization technique.
Assess how the candidate balances time complexity and space constraints in their approach.

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the correct parity at each index by improperly swapping or missing swaps for some elements.
Incorrect handling of boundary conditions, such as when pointers exceed array limits.
Using additional space for sorting unnecessarily, violating the space complexity requirement of O(1).

Follow-up variants

Handling cases with larger arrays where the time complexity becomes critical.
Handling edge cases with arrays where all elements are already sorted by parity.
Generalizing the two-pointer technique for arrays of odd length or arrays with other constraints.

FAQ

What is the best approach to solve the Sort Array By Parity II problem?

The best approach is to use a two-pointer technique, swapping elements at even and odd indices to ensure parity constraints are satisfied efficiently.

Why should I use two pointers for the Sort Array By Parity II problem?

Using two pointers allows you to process the array in linear time, ensuring that you can efficiently rearrange elements without requiring additional space.

What is the time complexity of the Sort Array By Parity II solution?

The time complexity of the solution is O(n), where n is the length of the array, as each element is processed exactly once.

Can the Sort Array By Parity II problem be solved without extra space?

Yes, the problem can be solved in-place using the two-pointer technique, requiring O(1) space.

How does GhostInterview help with solving the Sort Array By Parity II problem?

GhostInterview provides structured solutions that guide you through the two-pointer approach, ensuring optimal performance and clarity in your understanding.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to even and odd indices, respectively. Initially, $i = 0$ and $j = 1$.

1

2

3

4

5

6

7

8

9

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n, j = len(nums), 1
        for i in range(0, n, 2):
            if nums[i] % 2:
                while nums[j] % 2:
                    j += 2
                nums[i], nums[j] = nums[j], nums[i]
        return nums

Continue Practicing

#923 3sum with multiplicity #905 sort array by parity #948 bag of tokens