Sort Array By Parity

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atWiproAirtel

Sort Array By Parity is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (in-place two pointers), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort by parity) up.

Problem

Given an integer array nums, rearrange it so that all even numbers come before all odd numbers.

Return any array that satisfies this; the order inside the even group and inside the odd group does not matter.

Examples

Example 1

Input
nums = [3, 8, 5, 2]
Output
[2, 8, 5, 3]
Why
2 and 8 are even and come first. Other orders such as [8, 2, 3, 5] are accepted too.

Example 2

Input
nums = [7]
Output
[7]
Why
A single number is already arranged.

Example 3

Input
nums = [0, 6, 1]
Output
[0, 6, 1]
Why
0 counts as even; the array already has all evens before the odd number.

Constraints

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 5000
  • Any arrangement with all even numbers before all odd numbers is accepted.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort by parity)O(n log n)O(n)
Optimal (in-place two pointers)O(n)O(1)

1Brute force (sort by parity)

TimeO(n log n)A comparison sort, though only two distinct keys exist.
SpaceO(n)The boxed copy used for sorting.

Sort the numbers using their parity (n % 2) as the key: every even number has key 0 and every odd number key 1, so evens end up first.

  1. Copy the numbers into a sortable list.
  2. Sort by n % 2.
  3. Copy them back and return.
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        Integer[] boxed = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];
        Arrays.sort(boxed, (a, b) -> (a % 2) - (b % 2));
        int[] out = new int[nums.length];
        for (int i = 0; i < nums.length; i++) out[i] = boxed[i];
        return out;
    }
}

2Optimal (in-place two pointers)

TimeO(n)Each step moves at least one pointer, so there are at most n steps.
SpaceO(1)The array is rearranged in place.

Grow an even block from the left and an odd block from the right. The left pointer skips evens, the right pointer skips odds; when the left one sits on an odd number and the right one on an even number, swap them. Like one step of quicksort's partition.

  1. left = 0, right = n - 1.
  2. While left < right: if nums[left] is even, left++; else if nums[right] is odd, right--; else swap them and move both.
  3. Return nums.
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++;
            } else if (nums[right] % 2 == 1) {
                right--;
            } else {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

Edge cases to test

  • A single element
  • All even or all odd numbers
  • Zeros (0 is even)
  • Odds first, evens last (every element moves)

Hints

Hint 1

You only need two groups, not a full sort.

Hint 2

Use one pointer from the left that stops at an odd number and one from the right that stops at an even number. What should happen when both stop?

FAQ

What is the best time complexity for Sort Array By Parity?

Optimal (in-place two pointers) runs in O(n) time and O(1) extra space. Each step moves at least one pointer, so there are at most n steps.

Which pattern does Sort Array By Parity use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Sort Array By Parity?

Yes. Brute force (sort by parity) takes O(n log n) time and O(n) space. Sort the numbers using their parity (n % 2) as the key: every even number has key 0 and every odd number key 1, so evens end up first.

Which edge cases should I test for Sort Array By Parity?

A single element; All even or all odd numbers; Zeros (0 is even); Odds first, evens last (every element moves).