Scale Engineer

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 * 104
  • 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.
class Solution {    public int[] sortArrayByParityII(int[] nums) {        int n = nums.length;        int[] result = new int[n];        int evenIndex = 0;        int oddIndex = 1;        for (int num : nums) {            if (num % 2 == 0) {                result[evenIndex] = num;                evenIndex += 2;            } else {                result[oddIndex] = num;                oddIndex += 2;            }        }        return result;    }}

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.

Solutions

class Solution {public  int[] sortArrayByParityII(int[] nums) {    for (int i = 0, j = 1; i < nums.length; i += 2) {      if ((nums[i] & 1) == 1) {        while ((nums[j] & 1) == 1) {          j += 2;        }        int t = nums[i];        nums[i] = nums[j];        nums[j] = t;      }    }    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 →

Next problem