Sort Array By Parity II

Easy

#0876Time: O(N), where `N` is the number of elements in the array. We perform a single pass through the input array.Space: O(N), as we use an auxiliary array of size `N` to store the result.

Patterns

Two Pointers

Algorithms

Sorting

Data structures

Array

Prompt

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.

Example 1:

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.

Example 2:

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

Constraints:

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

Follow Up: Could you solve it in-place?

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to use an additional array to store the sorted elements. We can iterate through the input array, and based on the parity of each number, place it in the correct position in the new array.

Algorithm

Create a new integer array result with the same length as nums.
Initialize an evenIndex pointer to 0.
Initialize an oddIndex pointer to 1.
Iterate through each num in the input array nums.
If num is even (i.e., num % 2 == 0), assign result[evenIndex] = num and update evenIndex = evenIndex + 2.
If num is odd, assign result[oddIndex] = num and update oddIndex = oddIndex + 2.
After the loop finishes, return the result array.

Walkthrough

We can solve this problem by allocating a new array, result, of the same size as the input nums. We'll use two index pointers: evenIndex starting at 0 for placing even numbers, and oddIndex starting at 1 for placing odd numbers. We then iterate through each number in the input array nums.

If the number is even, we place it at result[evenIndex] and then increment evenIndex by 2.
If the number is odd, we place it at result[oddIndex] and then increment oddIndex by 2. After iterating through all the numbers in nums, the result array will be sorted according to the problem's criteria.

1class Solution {2    public int[] sortArrayByParityII(int[] nums) {3        int n = nums.length;4        int[] result = new int[n];5        int evenIndex = 0;6        int oddIndex = 1;7        for (int num : nums) {8            if (num % 2 == 0) {9                result[evenIndex] = num;10                evenIndex += 2;11            } else {12                result[oddIndex] = num;13                oddIndex += 2;14            }15        }16        return result;17    }18}

Complexity

Time

O(N), where `N` is the number of elements in the array. We perform a single pass through the input array.

Space

O(N), as we use an auxiliary array of size `N` to store the result.

Trade-offs

Pros

The logic is simple and easy to follow.
Implementation is straightforward.

Cons

It's not an in-place solution and requires extra memory, which can be a drawback for very large inputs.

To solve the problem in-place as suggested by the follow-up, we can use a two-pointer technique. One pointer, even, will iterate through the even indices, and another pointer, odd, will iterate through the odd indices. The goal is to find and swap misplaced elements.

Algorithm

Initialize a pointer even to 0 and a pointer odd to 1.
Enter a loop that continues as long as both even and odd are within the array bounds (< nums.length).
Inside the loop, advance the even pointer by 2 until it points to an odd number (nums[even] % 2 != 0) or goes out of bounds.
Similarly, advance the odd pointer by 2 until it points to an even number (nums[odd] % 2 == 0) or goes out of bounds.
If both pointers are still within the array bounds, it means we've found an odd number at an even index and an even number at an odd index. Swap nums[even] and nums[odd].
The loop continues until one of the pointers moves past the end of the array, at which point the array is correctly sorted.
Return the modified nums array.

Walkthrough

This approach modifies the array directly without using extra space. We use two pointers: even starting at index 0 and odd starting at index 1. The even pointer's job is to find the first even index i that holds an odd number (nums[i] % 2 != 0). It does this by advancing by 2 in each step (even += 2). Similarly, the odd pointer's job is to find the first odd index j that holds an even number (nums[j] % 2 == 0). It also advances by 2 in each step (odd += 2). Once both pointers have found a misplaced number, we swap nums[even] and nums[odd]. This places the even number at an even index and the odd number at an odd index, correcting their positions. We repeat this process until either pointer goes beyond the array's bounds. Since the input is guaranteed to have an equal number of even and odd numbers, this process will correctly sort the entire array.

1class Solution {2    public int[] sortArrayByParityII(int[] nums) {3        int n = nums.length;4        int even = 0;5        int odd = 1;6        7        while (even < n && odd < n) {8            // Find the first even index with an odd number9            while (even < n && nums[even] % 2 == 0) {10                even += 2;11            }12            13            // Find the first odd index with an even number14            while (odd < n && nums[odd] % 2 != 0) {15                odd += 2;16            }17            18            // If both pointers are valid, swap the elements19            if (even < n && odd < n) {20                int temp = nums[even];21                nums[even] = nums[odd];22                nums[odd] = temp;23            }24        }25        26        return nums;27    }28}

Complexity

Time

O(N), where `N` is the number of elements. Although there are nested loops, each pointer (`even` and `odd`) traverses its respective set of indices (even or odd) at most once. Therefore, each element is visited a constant number of times.

Space

O(1). The sorting is performed in-place, so no additional space proportional to the input size is required.

Trade-offs

Pros

Highly efficient in terms of space, satisfying the in-place requirement.
Maintains a linear time complexity.

Cons

The logic with two pointers and nested loops can be slightly more complex to reason about compared to the auxiliary array method.

Solutions

Solution

1class Solution {2public3  int[] sortArrayByParityII(int[] nums) {4    for (int i = 0, j = 1; i < nums.length; i += 2) {5      if ((nums[i] & 1) == 1) {6        while ((nums[j] & 1) == 1) {7          j += 2;8        }9        int t = nums[i];10        nums[i] = nums[j];11        nums[j] = t;12      }13    }14    return nums;15  }16}

1/** * @param {number[]} nums * @return {number[]} */ var sortArrayByParityII =2  function (nums) {3    for (let i = 0, j = 1; i < nums.length; i += 2) {4      if ((nums[i] & 1) == 1) {5        while ((nums[j] & 1) == 1) {6          j += 2;7        }8        [nums[i], nums[j]] = [nums[j], nums[i]];9      }10    }11    return nums;12  };

1class Solution {2public:3  vector<int> sortArrayByParityII(vector<int> &nums) {4    for (int i = 0, j = 1; i < nums.size(); i += 2) {5      if ((nums[i] & 1) == 1) {6        while ((nums[j] & 1) == 1) {7          j += 2;8        }9        swap(nums[i], nums[j]);10      }11    }12    return nums;13  }14};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem