💬 Discord
Sign In
NeetCode #188LC-905EasyTwo Pointers
← Back to All Problems

#188 · #905 · Sort Array By Parity(按奇偶排序数组)

📌 Problem Statement & Constraints

Given an integer array nums, move all even integers to the beginning followed by all odd integers, and return any array satisfying this. Constraints: 1 <= nums.length <= 5000, 0 <= nums[i] <= 5000.

💡 Core Algorithmic Approaches

  1. The relative order within the even and odd groups is not constrained, which allows a simple two-pointer swap.
  2. Keep a write pointer k for the next even slot and scan with i. When nums[i] is even, swap it into position k and advance k.
  3. Odd values naturally drift to the back as evens are swapped forward.
  4. A single pass suffices, and no sorting is needed.

💻 Benchmark Python3 Implementation

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        k = 0                          # next slot for an even number
        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[k], nums[i] = nums[i], nums[k]
                k += 1
        return nums

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): in place.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by parity with a comparator: O(n log n) and unnecessary, since the order within groups is unconstrained.
  • Building two lists and concatenating: correct but O(n) extra space.
  • Swapping when nums[i] is odd: only even values should be moved to the front.
  • Using nums[i] & 1 == 0: correct but % 2 == 0 is clearer for readability.