905. Sort Array By Parity

EasyView on LeetCode

Array Two Pointers Sorting

Time: O(n)

Space: O(1)

Problem Overview

Partition the array in-place so all even numbers appear before odd numbers.

Intuition

Partition the array in-place so all even numbers appear before odd numbers. Two pointers from both ends swap misplaced elements — even values belong on the left, odd on the right. Relative order within evens or odds does not need to be preserved.

Algorithm

1Set lo = 0, hi = n - 1.
2While lo < hi: if A[lo] is even, lo++. Else if A[hi] is odd, hi--. Else swap A[lo] and A[hi], then lo++ and hi--.
3Return the modified array.

Example Walkthrough

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

1.Swap 3 and 4 → [4,1,2,3]. lo advances past 4, hi past 3.
2.1 and 3 are odd/even pair → swap → [4,3,2,1] or similar partition.

Output: [4,2,3,1] (any valid even-before-odd order)

Common Pitfalls

•Use modulo 2 to test parity: n % 2 == 0.
•O(n) time, O(1) extra space — do not allocate a second array unless allowed.
•Stable order is not required by the problem.

905.cs

// Approach: In-place two-pointer partition; move even numbers to the front by swapping with a write pointer.
// Time: O(n) Space: O(1)

public class Solution
{
    public int[] SortArrayByParity(int[] nums)
    {
        int n = nums.Length;
        int k = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] % 2 == 0)
            {
                int temp = nums[k];
                nums[k++] = nums[i];
                nums[i] = temp;
            }
        }

        return nums;
    }
}

Was this solution helpful?