algoadvance

Given an array of integers nums, half of the integers in nums are odd, and the other half are even. The requirement is to sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Example:

Input: nums = [4, 2, 5, 7]
Output: [4, 5, 2, 7]
Explanation: [4, 7, 2, 5], [2, 5, 4, 7], and [2, 7, 4, 5] would also be correct.

Clarifying Questions

  1. Will the input array always contain half even numbers and half odd numbers?
    • Yes.
  2. Can the array length be zero?
    • No, it is guaranteed that there is at least one even and one odd number in the array.
  3. Should the solution be in-place, or can we use additional space?
    • Either solution is acceptable as long as it meets the problem constraints.

Strategy

We can use a two-pointer approach:

  1. One pointer (even_idx) will focus on even indices and will seek the next odd number located at an even index.
  2. Another pointer (odd_idx) will focus on odd indices and will seek the next even number located at an odd index.

We will then swap these misplaced numbers to ensure they are in the correct positions.

Code

def sortArrayByParityII(nums):
    n = len(nums)
    even_idx, odd_idx = 0, 1
    
    while even_idx < n and odd_idx < n:
        if nums[even_idx] % 2 == 0:
            even_idx += 2
        elif nums[odd_idx] % 2 == 1:
            odd_idx += 2
        else:
            # Swap the misplaced values
            nums[even_idx], nums[odd_idx] = nums[odd_idx], nums[even_idx]
            even_idx += 2
            odd_idx += 2
    
    return nums

# Example usage
print(sortArrayByParityII([4, 2, 5, 7]))  # Output could be [4, 5, 2, 7] or any other valid configuration

Time Complexity

This solution effectively rearranges the array by ensuring that all even indices contain even numbers and all odd indices contain odd numbers through a series of swaps.

Try our interview co-pilot at AlgoAdvance.com