Sort Array By Parity II

Difficulty: Easy | Acceptance: 71.30% | Paid: No Topics: Array, Two Pointers, Sorting

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

• Examples
• Constraints
• Approach 1: Two Pass with Extra Space
• Approach 2: In-Place Two Pointers

Examples

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Input: nums = [2,3]
Output: [2,3]

Constraints

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

Approach 1: Two Pass with Extra Space

Intuition We can separate the even and odd numbers into two different lists. Then, we iterate through the original array indices and place the even numbers at even indices and odd numbers at odd indices.

Steps

• Iterate through the input array and collect all even numbers into an evens list and all odd numbers into an odds list.
• Initialize an index e for evens and o for odds to 0.
• Iterate through the original array from i = 0 to n-1.
• If i is even, assign nums[i] = evens[e] and increment e.
• If i is odd, assign nums[i] = odds[o] and increment o.
• Return the modified array.

class Solution:
    def sortArrayByParityII(self, nums: list[int]) -> list[int]:
        evens = [x for x in nums if x % 2 == 0]
        odds = [x for x in nums if x % 2 != 0]
        
        e, o = 0, 0
        for i in range(len(nums)):
            if i % 2 == 0:
                nums[i] = evens[e]
                e += 1
            else:
                nums[i] = odds[o]
                o += 1
        return nums

Complexity

• Time: O(N) where N is the length of the array. We iterate through the array a constant number of times.
• Space: O(N) to store the separate lists of even and odd numbers.
• Notes: This approach is straightforward and easy to understand but uses extra memory proportional to the input size.

Approach 2: In-Place Two Pointers

Intuition We can solve this in-place using two pointers. One pointer i iterates over even indices (0, 2, 4…), and another pointer j iterates over odd indices (1, 3, 5…). If nums[i] is odd, it means an odd number is at an even index. We then look for the next even number at an odd index j and swap them.

Steps

• Initialize pointer i = 0 (for even indices) and j = 1 (for odd indices).
• Iterate while j < n (since j starts at 1, it covers the array bounds).
• If nums[i] is even, it is at the correct place, so increment i by 2.
• Else if nums[j] is odd, it is at the correct place, so increment j by 2.
• Else, nums[i] is odd and nums[j] is even. Swap nums[i] and nums[j]. Then increment both i and j by 2.
• Return the array.

class Solution:
    def sortArrayByParityII(self, nums: list[int]) -> list[int]:
        i, j = 0, 1
        n = len(nums)
        
        while j < n:
            # If even index has even number, skip to next even index
            if nums[i] % 2 == 0:
                i += 2
            # If odd index has odd number, skip to next odd index
            elif nums[j] % 2 != 0:
                j += 2
            # Even index has odd, Odd index has even -> Swap
            else:
                nums[i], nums[j] = nums[j], nums[i]
                i += 2
                j += 2
                
        return nums

Complexity

• Time: O(N) where N is the length of the array. Each pointer traverses the array at most once.
• Space: O(1) as we modify the array in-place without using extra data structures.
• Notes: This is the optimal solution in terms of space complexity.