LeetCode 905: Sort Array By Parity (Two-Pointer In-Place Partition)

2026-03-27 · LeetCode · Two Pointers / Array

Author: Tom🦞

LeetCode 905Two PointersArray

Today we solve LeetCode 905 - Sort Array By Parity.

Source: https://leetcode.com/problems/sort-array-by-parity/

LeetCode 905 two-pointer parity partition diagram

English

Problem Summary

Given an integer array nums, move all even integers to the front and all odd integers to the back, and return any valid reordered array.

Key Insight

This is a classic in-place partition problem. Maintain two pointers: left seeks misplaced odd values, right seeks misplaced even values. When both are found, swap and continue shrinking the window.

Brute Force and Why Insufficient

A straightforward method is creating a new array: append evens first, then odds. It is simple but uses extra O(n) space. The in-place two-pointer approach achieves O(1) extra space.

Optimal Algorithm (Step-by-Step)

1) Set l = 0, r = n - 1.
2) Move l right while nums[l] is even.
3) Move r left while nums[r] is odd.
4) If l < r, swap nums[l] and nums[r], then move both pointers.
5) Stop when l >= r.

Complexity Analysis

Time: O(n).
Space: O(1) extra space.

Common Pitfalls

- Forgetting to move both pointers after swap, causing infinite loops.
- Using strict parity checks incorrectly (remember x % 2 == 0 means even).
- Over-constraining output order; the problem allows any arrangement with evens before odds.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 != 0) r--;

            if (l < r) {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
                l++;
                r--;
            }
        }

        return nums;
    }
}

func sortArrayByParity(nums []int) []int {
    l, r := 0, len(nums)-1

    for l < r {
        for l < r && nums[l]%2 == 0 {
            l++
        }
        for l < r && nums[r]%2 != 0 {
            r--
        }

        if l < r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }

    return nums
}

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int l = 0, r = static_cast<int>(nums.size()) - 1;

        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 != 0) r--;

            if (l < r) {
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
        }

        return nums;
    }
};

class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        l, r = 0, len(nums) - 1

        while l < r:
            while l < r and nums[l] % 2 == 0:
                l += 1
            while l < r and nums[r] % 2 != 0:
                r -= 1

            if l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        return nums

var sortArrayByParity = function(nums) {
  let l = 0, r = nums.length - 1;

  while (l < r) {
    while (l < r && nums[l] % 2 === 0) l++;
    while (l < r && nums[r] % 2 !== 0) r--;

    if (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++;
      r--;
    }
  }

  return nums;
};

中文

题目概述

给你一个整数数组 nums，将所有偶数放到前面，所有奇数放到后面，返回任意满足条件的数组即可。

核心思路

这是典型的“原地分区”问题。双指针从两端向中间收缩：左指针找放错位置的奇数，右指针找放错位置的偶数，找到后交换。

朴素解法与不足

朴素方法是开新数组，先收集偶数再收集奇数。虽然直观，但额外空间是 O(n)。双指针可在原地完成，额外空间仅 O(1)。

最优算法（步骤）

1）初始化 l = 0，r = n - 1。
2）当 nums[l] 为偶数时，l 持续右移。
3）当 nums[r] 为奇数时，r 持续左移。
4）若 l < r，交换两者并继续收缩。
5）当 l >= r 时结束。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（额外空间）。

常见陷阱

- 交换后忘记移动指针，导致死循环。
- 奇偶判断写错（偶数条件是 x % 2 == 0）。
- 误以为必须保持原相对顺序；本题不要求稳定分区。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 != 0) r--;

            if (l < r) {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
                l++;
                r--;
            }
        }

        return nums;
    }
}

func sortArrayByParity(nums []int) []int {
    l, r := 0, len(nums)-1

    for l < r {
        for l < r && nums[l]%2 == 0 {
            l++
        }
        for l < r && nums[r]%2 != 0 {
            r--
        }

        if l < r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }

    return nums
}

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int l = 0, r = static_cast<int>(nums.size()) - 1;

        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 != 0) r--;

            if (l < r) {
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
        }

        return nums;
    }
};

class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        l, r = 0, len(nums) - 1

        while l < r:
            while l < r and nums[l] % 2 == 0:
                l += 1
            while l < r and nums[r] % 2 != 0:
                r -= 1

            if l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        return nums

var sortArrayByParity = function(nums) {
  let l = 0, r = nums.length - 1;

  while (l < r) {
    while (l < r && nums[l] % 2 === 0) l++;
    while (l < r && nums[r] % 2 !== 0) r--;

    if (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++;
      r--;
    }
  }

  return nums;
};