LeetCode 922 - Sort Array By Parity II

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

The problem gives an integer array nums where exactly half of the elements are even numbers and the other half are odd numbers. The task is to rearrange the array so that every even index contains an even number and every odd index contains an odd number.

In other words:

If an index i is even, then nums[i] must also be even.
If an index i is odd, then nums[i] must also be odd.

The problem guarantees that a valid arrangement always exists because the array contains equal counts of even and odd numbers, and the total length of the array is even.

For example, given:

nums = [4,2,5,7]

there are two even numbers (4, 2) and two odd numbers (5, 7). A valid rearrangement is:

[4,5,2,7]

because:

index 0 is even and contains 4 which is even
index 1 is odd and contains 5 which is odd
index 2 is even and contains 2 which is even
index 3 is odd and contains 7 which is odd

The constraints are important because they guide the expected efficiency of the solution:

nums.length can be as large as 2 * 10^4
the array length is always even
exactly half the values are even and half are odd
values are small integers, but their magnitude is irrelevant because only parity matters

These constraints strongly suggest that an O(n) solution is ideal. Since the follow-up specifically asks whether the solution can be done in-place, minimizing extra memory is also desirable.

Several edge cases are important to recognize upfront. The smallest possible input has only two elements, such as [2,3]. Another important case is when the array is already correctly arranged, because the algorithm should avoid breaking a valid configuration. A more subtle case occurs when many values are misplaced, such as all even numbers appearing in odd positions and vice versa. The problem guarantees equal counts of odd and even numbers, so we never need to handle impossible inputs.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to separate all even numbers and all odd numbers into two temporary lists. Once separated, we can rebuild the result array by placing even numbers into even indices and odd numbers into odd indices.

The process works as follows:

Traverse the array once.
Store all even numbers in one list.
Store all odd numbers in another list.
Create a result array.
Fill even indices using the even list.
Fill odd indices using the odd list.

This approach is easy to understand and guarantees correctness because the problem already guarantees equal numbers of even and odd elements.

However, this solution uses additional memory proportional to the input size. While the time complexity is efficient, the follow-up asks whether the problem can be solved in-place, so we can do better in terms of space usage.

Optimal Two Pointer Approach

The key observation is that we do not need to fully sort the array. We only need to ensure that parity matches the index parity.

This suggests a two-pointer strategy:

One pointer scans even indices looking for incorrectly placed odd numbers.
Another pointer scans odd indices looking for incorrectly placed even numbers.
Whenever both misplaced values are found, swap them.

This works because:

An odd number in an even position must eventually move to an odd position.
An even number in an odd position must eventually move to an even position.
Swapping these two incorrect values fixes both positions simultaneously.

Since each pointer moves only forward and every element is processed at most once, the algorithm runs in linear time and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses separate even and odd lists to rebuild the array
Optimal	O(n)	O(1)	Uses two pointers and swaps misplaced elements in-place

Algorithm Walkthrough

Optimal Two Pointer Algorithm

Initialize one pointer even_index to 0. This pointer will only move across even indices.
Initialize another pointer odd_index to 1. This pointer will only move across odd indices.
Traverse the array using even_index. At every even position, check whether the value is correctly placed.
If nums[even_index] is even, then this position is already valid. Move even_index forward by 2.
If nums[even_index] is odd, then this value is misplaced because an even index must contain an even number.
Now search for an incorrectly placed even number in an odd index. Move odd_index forward by 2 until nums[odd_index] is even.
Once both misplaced elements are found:

nums[even_index] is odd and wrongly placed
nums[odd_index] is even and wrongly placed

Swap them. 8. After swapping:

the even index now contains an even number
the odd index now contains an odd number

Continue until all even indices have been processed.

Why it works

The algorithm maintains an important invariant: every processed even index contains an even number, and every processed odd index contains an odd number.

Whenever a mismatch is found, the algorithm locates the complementary mismatch and swaps the two elements. Since the counts of even and odd numbers are equal, a matching misplaced element must always exist. Each swap fixes two incorrect positions at once, guaranteeing that the final array satisfies the parity condition.

Python Solution

from typing import List

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        even_index = 0
        odd_index = 1
        n = len(nums)

        while even_index < n:
            # If the current even index already contains an even number,
            # move to the next even index.
            if nums[even_index] % 2 == 0:
                even_index += 2
                continue

            # Find an odd index containing an even number.
            while nums[odd_index] % 2 == 1:
                odd_index += 2

            # Swap misplaced numbers.
            nums[even_index], nums[odd_index] = (
                nums[odd_index],
                nums[even_index],
            )

            even_index += 2

        return nums

The implementation follows the exact logic described in the algorithm walkthrough.

The variable even_index scans only even positions. Whenever it encounters an odd number, we know that position is invalid.

The variable odd_index scans only odd positions searching for an even number that is also incorrectly placed.

Once both mismatches are identified, the swap fixes two positions simultaneously. Because each pointer advances only forward and skips already-correct positions, the algorithm remains efficient.

The solution modifies the input array directly, which satisfies the follow-up requirement for an in-place algorithm.

Go Solution

func sortArrayByParityII(nums []int) []int {
	evenIndex := 0
	oddIndex := 1
	n := len(nums)

	for evenIndex < n {
		// Correct placement for even index
		if nums[evenIndex]%2 == 0 {
			evenIndex += 2
			continue
		}

		// Find misplaced even number at odd index
		for nums[oddIndex]%2 == 1 {
			oddIndex += 2
		}

		// Swap misplaced values
		nums[evenIndex], nums[oddIndex] = nums[oddIndex], nums[evenIndex]

		evenIndex += 2
	}

	return nums
}

The Go implementation is nearly identical to the Python version. The primary difference is syntax.

Go slices are mutable, so swaps modify the original slice directly. There is no need for special handling of empty or nil slices because the constraints guarantee at least two elements. Integer overflow is not a concern because the algorithm only performs parity checks and index movement.

Worked Examples

Example 1

Input:

nums = [4,2,5,7]

Initial state:

Step	even_index	odd_index	Array	Action
Start	0	1	[4,2,5,7]	Begin traversal

Check index 0:

nums[0] = 4
4 is even
position is valid

Move even_index to 2.

Step	even_index	odd_index	Array	Action
1	2	1	[4,2,5,7]	Check even index 2

Check index 2:

nums[2] = 5
5 is odd
incorrect placement

Now search odd indices for a misplaced even number.

Check index 1:

nums[1] = 2
2 is even
incorrect placement at odd index

Swap nums[2] and nums[1].

Step	even_index	odd_index	Array	Action
2	2	1	[4,5,2,7]	Swap misplaced elements

Move even_index to 4.

Traversal ends because 4 >= len(nums).

Final result:

[4,5,2,7]

Example 2

Input:

nums = [2,3]

Initial state:

Step	even_index	odd_index	Array	Action
Start	0	1	[2,3]	Begin traversal

Check index 0:

nums[0] = 2
already correct

Move even_index to 2.

Traversal ends.

Final result:

[2,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves through the array at most once
Space	O(1)	Only a few extra variables are used

The time complexity is linear because both pointers only move forward through the array. No index is revisited unnecessarily.

The space complexity is constant because the algorithm performs swaps directly within the input array and uses only a small number of variables regardless of input size.

Test Cases

from typing import List

def is_valid(arr: List[int]) -> bool:
    for i, value in enumerate(arr):
        if i % 2 != value % 2:
            return False
    return True

solution = Solution()

# Provided example
result = solution.sortArrayByParityII([4, 2, 5, 7])
assert is_valid(result)  # standard mixed case

# Smallest valid input
result = solution.sortArrayByParityII([2, 3])
assert is_valid(result)  # minimum array size

# Already correctly arranged
result = solution.sortArrayByParityII([2, 1, 4, 3])
assert is_valid(result)  # should remain valid

# Completely misplaced values
result = solution.sortArrayByParityII([1, 2, 3, 4])
assert is_valid(result)  # every position initially incorrect

# Larger alternating pattern
result = solution.sortArrayByParityII([6, 1, 8, 3, 10, 5, 12, 7])
assert is_valid(result)  # larger valid configuration

# Many swaps required
result = solution.sortArrayByParityII([1, 4, 3, 2, 5, 6, 7, 8])
assert is_valid(result)  # repeated corrections needed

# Duplicate values
result = solution.sortArrayByParityII([2, 2, 1, 1])
assert is_valid(result)  # handles duplicates correctly

# Larger stress-style case
result = solution.sortArrayByParityII(
    [1, 0, 3, 2, 5, 4, 7, 6, 9, 8]
)
assert is_valid(result)  # multiple misplaced pairs

Test	Why
`[4,2,5,7]`	Validates the standard example
`[2,3]`	Tests the smallest possible input
`[2,1,4,3]`	Ensures already-correct arrays remain valid
`[1,2,3,4]`	Tests fully misplaced parity positions
`[6,1,8,3,10,5,12,7]`	Tests larger correctly arranged input
`[1,4,3,2,5,6,7,8]`	Verifies repeated swapping logic
`[2,2,1,1]`	Ensures duplicates are handled properly
`[1,0,3,2,5,4,7,6,9,8]`	Stress-style parity correction case

Edge Cases

One important edge case is the minimum-sized array, such as [2,3]. Small inputs often expose off-by-one errors or incorrect loop conditions. In this implementation, the loop condition even_index < n ensures safe traversal, and the algorithm correctly terminates after processing the only even index.

Another important case is an array that is already valid, such as [2,1,4,3]. A buggy implementation might perform unnecessary swaps or accidentally disrupt correct placements. This solution avoids that issue because it immediately skips correctly placed elements.

A more challenging case occurs when nearly every element is misplaced, such as [1,2,3,4]. In this scenario, the algorithm must repeatedly search for complementary mismatches and swap them correctly. The two-pointer approach handles this naturally because every swap fixes one incorrect even position and one incorrect odd position simultaneously.

Duplicate values are also important to consider. Arrays like [2,2,1,1] verify that the algorithm depends only on parity, not uniqueness. Since the logic checks only whether numbers are odd or even, duplicates are handled correctly without any special treatment.