Scale Engineer

Sort Array By Parity

Easy
#0859Time: O(N log N). The dominant operation is the sort, which typically has this time complexity. The conversions to and from `Integer[]` take O(N) time.Space: O(N). We need an auxiliary array of `Integer` objects to use the custom comparator with `Arrays.sort`.1 company
Patterns
Two Pointers
Algorithms
Sorting
Data structures
Array
Companies
DXC Technology

Prompt

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

 

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

 

Constraints:

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 5000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach treats the problem as a custom sorting problem. We can use a standard sorting algorithm, but with a custom comparison logic. The logic is simple: even numbers are considered "smaller" than odd numbers. This ensures that after sorting, all even numbers will appear before all odd numbers.

Algorithm

  • Create a new Integer array of the same size as the input nums array.
  • Copy the elements from nums to the new Integer array.
  • Use Arrays.sort() with a custom lambda comparator: (a, b) -> Integer.compare(a % 2, b % 2). This sorts the array by placing even numbers (where x % 2 is 0) before odd numbers (where x % 2 is 1).
  • Copy the sorted elements from the Integer array back to the original nums array.
  • Return the modified nums array.

Walkthrough

The core idea is to define a custom comparator that guides the sorting process. The comparator for two numbers, a and b, will return a negative value if a should come before b, a positive value if b should come before a, and zero if their order doesn't matter relative to the parity rule. The comparison can be based on the result of the modulo-2 operation (x % 2). An even number gives 0, and an odd number gives 1. So, we can simply sort based on a % 2 vs b % 2. In Java, Arrays.sort() on primitive arrays doesn't accept a custom comparator. A common way to handle this is to convert the int[] to an Integer[], sort the Integer[], and then copy it back.

import java.util.Arrays; class Solution {    public int[] sortArrayByParity(int[] nums) {        Integer[] numsInteger = new Integer[nums.length];        for (int i = 0; i < nums.length; i++) {            numsInteger[i] = nums[i];        }         Arrays.sort(numsInteger, (a, b) -> Integer.compare(a % 2, b % 2));         for (int i = 0; i < nums.length; i++) {            nums[i] = numsInteger[i];        }        return nums;    }}

Complexity

Time

O(N log N). The dominant operation is the sort, which typically has this time complexity. The conversions to and from `Integer[]` take O(N) time.

Space

O(N). We need an auxiliary array of `Integer` objects to use the custom comparator with `Arrays.sort`.

Trade-offs

Pros

  • Conceptually simple and relies on a well-known library function.

  • The code is concise and easy to write.

Cons

  • Not the most efficient time complexity for this specific problem.

  • Requires extra space for the boxed Integer array, which also adds overhead.

Solutions

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