Problem Description

You are given an array of integers nums where exactly half of the integers are odd numbers and the other half are even numbers.

Your task is to rearrange the array so that:

• Elements at even indices (0, 2, 4, ...) are even numbers
• Elements at odd indices (1, 3, 5, ...) are odd numbers

In other words, if i is even, then nums[i] should be even, and if i is odd, then nums[i] should be odd.

You can return any valid arrangement that satisfies this condition.

For example, if nums = [4, 2, 5, 7], one valid output would be [4, 5, 2, 7] where:

• Index 0 (even): contains 4 (even) ✓
• Index 1 (odd): contains 5 (odd) ✓
• Index 2 (even): contains 2 (even) ✓
• Index 3 (odd): contains 7 (odd) ✓

The solution uses a two-pointer technique where pointer i traverses even indices (0, 2, 4, ...) and pointer j traverses odd indices (1, 3, 5, ...). When an even index contains an odd number, it finds an odd index containing an even number and swaps them. This ensures that all elements end up in their correct positions according to the parity rules.

Intuition

Since we know that exactly half of the numbers are even and half are odd, and we have exactly half even indices and half odd indices, there's a perfect one-to-one mapping possible between even numbers and even indices, as well as odd numbers and odd indices.

The key insight is that we don't need to sort or use extra space - we just need to fix misplaced elements. If we find an even number at an odd index, we know there must be a corresponding odd number somewhere at an even index (since the counts are balanced). These two elements are both in wrong positions and can be fixed by swapping them.

We can approach this systematically by checking even indices one by one. When we find an odd number at an even index (position i), it's misplaced. We then need to find its swap partner - an even number that's sitting at some odd index. Once we find such a pair, swapping them fixes both positions simultaneously.

Why start searching from odd index j = 1 and increment by 2? Because we're looking through odd indices for even numbers. Once we've swapped an element at odd index j, we know it now contains an odd number (which is correct), so we don't need to check it again. This is why j only moves forward and never resets - each odd index is fixed at most once.

The algorithm is efficient because:

1. Each even index is visited exactly once (loop iteration)
2. Each odd index is checked at most once (the while loop advances j without going back)
3. Each swap fixes two positions permanently

This gives us an O(n) time complexity with O(1) space, making it an optimal in-place solution.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution uses a two-pointer technique to rearrange the array in-place. Here's how the implementation works:

Initialize Pointers:

• Set i = 0 to traverse even indices (0, 2, 4, ...)
• Set j = 1 to traverse odd indices (1, 3, 5, ...)

Main Loop: The algorithm iterates through all even indices using for i in range(0, n, 2):

1. Check if correction needed: At each even index i, check if nums[i] % 2 is non-zero (meaning the number is odd and misplaced).

2. Find swap partner: If nums[i] is odd, we need to find an even number at an odd index. Use a while loop to advance j:

   while nums[j] % 2:
       j += 2

   This loop skips over odd indices that already contain odd numbers (which are correctly placed) until it finds an even number at an odd index.

3. Perform swap: Once we find an even number at odd index j, swap it with the odd number at even index i:

   nums[i], nums[j] = nums[j], nums[i]

   After this swap:

   • Position i (even index) now contains an even number ✓
   • Position j (odd index) now contains an odd number ✓

Why this works:

• The pointer j never needs to reset because once an odd index is fixed (contains an odd number), it never needs to be checked again
• Since exactly half the numbers are even and half are odd, we're guaranteed to find a matching swap partner for every misplaced element
• Each element is moved at most once, making this an efficient single-pass solution

Time Complexity: O(n) - each index is visited at most once Space Complexity: O(1) - only using two pointer variables, modifying the array in-place

Example Walkthrough

Let's trace through the algorithm with nums = [3, 1, 4, 2]:

Initial State:

• Array: [3, 1, 4, 2]
• i = 0 (for even indices)
• j = 1 (for odd indices)

Step 1: Check index 0

• i = 0, nums[0] = 3 (odd number at even index - needs fixing!)
• Since 3 is odd (3 % 2 = 1), we need to find a swap partner
• Start searching from j = 1:
  • nums[1] = 1 (odd) - skip, increment j to 3
  • nums[3] = 2 (even) - found our swap partner!
• Swap nums[0] and nums[3]: [3, 1, 4, 2] → [2, 1, 4, 3]
• Now index 0 has 2 (even) ✓ and index 3 has 3 (odd) ✓

Step 2: Check index 2

• Move to next even index: i = 2
• nums[2] = 4 (even number at even index - already correct!)
• Since 4 is even (4 % 2 = 0), no action needed
• Skip to next iteration

Final Result: [2, 1, 4, 3]

Verification:

• Index 0 (even): 2 (even) ✓
• Index 1 (odd): 1 (odd) ✓
• Index 2 (even): 4 (even) ✓
• Index 3 (odd): 3 (odd) ✓

Notice how:

1. We only needed one swap to fix two misplaced elements
2. The pointer j moved forward from 1 to 3 and never went backward
3. Each position was checked/fixed exactly once

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm uses two pointers: i iterates through even indices (0, 2, 4, ...) and j iterates through odd indices (1, 3, 5, ...). The outer loop runs through all even indices, which is n/2 iterations. For each iteration where nums[i] is odd, the inner while loop advances j to find the next even number at an odd index. Since j only moves forward and never resets, each element at an odd index is visited at most once throughout the entire execution. Therefore, the total number of operations is at most n/2 (for the outer loop) plus n/2 (for the total movement of j), resulting in O(n) time complexity.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for the variables n, j, and i. The sorting is done in-place by swapping elements directly in the input array without requiring any additional data structures. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds Error

The most common pitfall occurs when the inner while loop advances the odd_index pointer without bounds checking:

# Dangerous code - can go out of bounds!
while nums[odd_index] % 2 == 1:
    odd_index += 2  # What if odd_index >= n?

Why this happens: If the input array is already partially sorted or has a specific pattern, the odd_index might advance beyond the array length before finding a suitable swap partner.

Solution: Add a bounds check to the while loop condition:

while odd_index < n and nums[odd_index] % 2 == 1:
    odd_index += 2

2. Incorrect Initial Assumption

Developers might assume they need to check both even and odd positions independently, leading to unnecessary complexity:

# Overly complex approach
for i in range(0, n, 2):
    if nums[i] % 2 == 1:
        # Find and swap...
      
for j in range(1, n, 2):  # Redundant second pass!
    if nums[j] % 2 == 0:
        # Find and swap...

Why this is wrong: Once you fix all even positions, the odd positions are automatically correct due to the constraint that exactly half are even and half are odd.

3. Resetting the Odd Pointer

Some might incorrectly reset the odd_index pointer for each iteration:

for even_index in range(0, n, 2):
    if nums[even_index] % 2 == 1:
        odd_index = 1  # Wrong! Don't reset
        while nums[odd_index] % 2 == 1:
            odd_index += 2

Why this is inefficient: Once an odd index contains an odd number (correctly placed), it never needs to be checked again. Resetting causes unnecessary re-checking and degrades performance from O(n) to O(n²) in worst case.

4. Missing Edge Case Validation

Not handling the case where the input might already be correctly arranged:

# Better implementation with early termination
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n = len(nums)
        odd_index = 1
      
        for even_index in range(0, n, 2):
            # Only proceed if correction is needed
            if nums[even_index] % 2 == 1:
                # Find next misplaced even number at odd index
                while odd_index < n and nums[odd_index] % 2 == 1:
                    odd_index += 2
              
                # Perform swap only if valid index found
                if odd_index < n:
                    nums[even_index], nums[odd_index] = nums[odd_index], nums[even_index]
      
        return nums

This implementation handles all edge cases while maintaining O(n) time complexity.