#905

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Sort Array By Parity

Reorder an integer array so all even numbers come before odd numbers using a precise two-pointer scanning method.

Problem Statement

Given an integer array nums, rearrange it so that all even integers appear before all odd integers. You must preserve the relative positions of evens and odds only as necessary for parity separation, and return any valid arrangement.

For example, given nums = [3,1,2,4], a correct output would be [2,4,3,1]. Any ordering that places all even numbers before odd numbers, like [4,2,1,3], is also valid. Constraints: 1 <= nums.length <= 5000, 0 <= nums[i] <= 5000.

Examples

Example 1

Input: nums = [3,1,2,4]

Output: [2,4,3,1]

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]

Example details omitted.

Constraints

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

Solution Approach

Two-Pointer Scanning

Use two pointers, left starting at index 0 and right scanning through the array. Swap nums[left] with nums[right] whenever nums[right] is even, then increment left. This keeps all evens on the left and tracks the next position for an even number.

Invariant Tracking

Maintain the invariant that all indices before the left pointer contain even numbers. Each swap preserves this condition, ensuring the algorithm never misplaces previously scanned elements. This prevents common off-by-one errors and redundant swaps.

Linear Pass Efficiency

Iterate through the array exactly once, performing constant-time operations per element. This guarantees O(n) time complexity and O(1) additional space, making it efficient even for the upper bound of 5000 elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The algorithm performs a single linear pass over the array, resulting in O(n) time. Only a few pointers are used without extra arrays, yielding O(1) additional space.

What Interviewers Usually Probe

Look for candidate solutions using two pointers and minimal swaps.
Ask about maintaining invariants to ensure no even numbers are lost in placement.
Probe edge cases like arrays with all even or all odd numbers.

Common Pitfalls or Variants

Common pitfalls

Swapping incorrectly when both pointers point to even numbers, causing unnecessary operations.
Forgetting to increment the left pointer after a successful swap, breaking the invariant.
Assuming stability is required when any valid ordering suffices, leading to extra complexity.

Follow-up variants

Sort array by parity while preserving original relative order of even and odd numbers (stable version).
Move all multiples of k to the front while keeping the rest in any order, generalizing the parity pattern.
Sort array into multiple partitions based on modulo classes instead of just even/odd separation.

FAQ

What is the fastest way to solve Sort Array By Parity using two pointers?

Use a left pointer to track the next even placement and a right pointer to scan through the array. Swap when an even number is found and increment the left pointer.

Do I need to preserve the original order of numbers?

No, any arrangement where all even numbers appear before all odd numbers is acceptable unless a stable version is specifically requested.

What are common mistakes when using the two-pointer method?

Forgetting to increment the left pointer after a swap, swapping unnecessarily, and mismanaging the invariant tracking are typical errors.

Can this algorithm handle arrays of length 1?

Yes, a single-element array is already correctly partitioned by parity, so the algorithm simply returns it.

What is the time and space complexity of this approach?

It runs in O(n) time with O(1) extra space because each element is visited once and only a few pointers are maintained.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the beginning and end of the array respectively. When $i < j$, we perform the following operations.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] % 2 == 0:
                i += 1
            elif nums[j] % 2 == 1:
                j -= 1
            else:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        return nums

Continue Practicing

#922 sort array by parity ii #923 3sum with multiplicity #881 boats to save people