Problem Description

You are given an integer array nums. Your task is to rearrange the array so that all even integers appear before all odd integers.

The problem asks you to move all even numbers to the beginning of the array, followed by all odd numbers. The order of even numbers among themselves doesn't matter, and the same applies to odd numbers. You just need to ensure that the array is partitioned into two sections: evens first, then odds.

For example:

• If nums = [3, 1, 2, 4], a valid output could be [2, 4, 3, 1] or [4, 2, 1, 3]
• The key requirement is that all even numbers (2 and 4) come before all odd numbers (3 and 1)

You need to return any array that satisfies this condition - there can be multiple correct answers since the relative order within even and odd groups doesn't matter.

Intuition

The key insight is that we need to partition the array into two groups: evens and odds. This is similar to the classic partitioning problem where we want to separate elements based on a condition.

Think about it this way: we want all evens on the left side and all odds on the right side. We can use two pointers starting from opposite ends of the array. The left pointer (i) will look for odd numbers that are in the "wrong" position (they should be on the right), and the right pointer (j) will look for even numbers that are in the "wrong" position (they should be on the left).

When we find an odd number on the left (where evens should be) and an even number on the right (where odds should be), we've found two elements that are both in the wrong sections. By swapping them, we fix both positions at once.

The beauty of this approach is that we're working from both ends toward the middle:

• If the left element is already even, it's in the correct position, so we move the left pointer forward
• If the right element is already odd, it's in the correct position, so we move the right pointer backward
• When we find a misplaced pair (odd on left, even on right), we swap them and move both pointers

This way, we only need to traverse the array once, making it an efficient O(n) solution with O(1) extra space since we're modifying the array in-place.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

We implement the two-pointer technique to partition the array in-place. Here's how the algorithm works:

1. Initialize two pointers: Set i = 0 pointing to the start of the array and j = len(nums) - 1 pointing to the end.

2. Process elements while pointers haven't crossed (i < j):

   • Case 1: If nums[i] % 2 == 0 (even number at left position)
     • This element is already in the correct section, so increment i by 1 to check the next element
   • Case 2: If nums[j] % 2 == 1 (odd number at right position)
     • This element is already in the correct section, so decrement j by 1 to check the previous element
   • Case 3: If neither of the above conditions is true
     • This means nums[i] is odd (should be on the right) and nums[j] is even (should be on the left)
     • Swap nums[i] and nums[j] to place both elements in their correct sections
     • Move both pointers: increment i by 1 and decrement j by 1

3. Return the modified array: After the loop completes, all even numbers will be on the left side and all odd numbers on the right side.

The algorithm efficiently partitions the array with a single pass, achieving O(n) time complexity where n is the length of the array. The space complexity is O(1) since we only use two pointer variables and modify the array in-place.

Example Walkthrough

Let's walk through the solution with nums = [3, 1, 2, 4]:

Initial State:

• Array: [3, 1, 2, 4]
• i = 0 (pointing to 3)
• j = 3 (pointing to 4)

Step 1: Check i < j (0 < 3) ✓

• nums[0] = 3 is odd (3 % 2 = 1) - not even, so Case 1 doesn't apply
• nums[3] = 4 is even (4 % 2 = 0) - not odd, so Case 2 doesn't apply
• Both elements are misplaced! Case 3: Swap them
• After swap: [4, 1, 2, 3]
• Move pointers: i = 1, j = 2

Step 2: Check i < j (1 < 2) ✓

• nums[1] = 1 is odd (1 % 2 = 1) - not even, so Case 1 doesn't apply
• nums[2] = 2 is even (2 % 2 = 0) - not odd, so Case 2 doesn't apply
• Both elements are misplaced! Case 3: Swap them
• After swap: [4, 2, 1, 3]
• Move pointers: i = 2, j = 1

Step 3: Check i < j (2 < 1) ✗

• The pointers have crossed, so we stop

Final Result: [4, 2, 1, 3]

• Even numbers (4, 2) are on the left
• Odd numbers (1, 3) are on the right
• The partitioning is complete!

The algorithm successfully partitioned the array with just 2 swaps, placing all even integers before all odd integers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm uses a two-pointer approach where pointer i starts from the beginning and pointer j starts from the end of the array. In each iteration, at least one pointer moves closer to the other (either i increments, j decrements, or both move when a swap occurs). Since the pointers converge and each element is visited at most once, the total number of operations is proportional to n.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the two pointer variables i and j, regardless of the input size. The sorting is done in-place by swapping elements within the original array, so no additional arrays or data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pointer Movement After Swap

A common mistake is moving only one pointer or forgetting to move pointers after swapping elements. This can lead to infinite loops or incorrect results.

Incorrect Implementation:

while left < right:
    if nums[left] % 2 == 0:
        left += 1
    elif nums[right] % 2 == 1:
        right -= 1
    else:
        nums[left], nums[right] = nums[right], nums[left]
        # Forgot to move pointers! This causes infinite loop

Solution: Always move both pointers after a swap since you know both elements are now correctly positioned.

2. Using <= Instead of < in While Condition

Using while left <= right instead of while left < right can cause unnecessary operations when pointers meet at the same index.

Why it matters: When left == right, we're looking at the same element, and no swap is needed. The element is already in its final position regardless of whether it's even or odd.

Correct approach: Use while left < right to stop when pointers meet or cross.

3. Checking Only One Condition Before Swapping

Some implementations might check only if the left element is odd before swapping, assuming the right element must be even:

Incorrect Implementation:

while left < right:
    if nums[left] % 2 == 1:  # Only checking if left is odd
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    else:
        left += 1

Problem: This doesn't account for when the right element is also odd. You'd swap two odd numbers unnecessarily and might miss even numbers on the right side.

Solution: Check both conditions separately (even on left, odd on right) before deciding to swap, as shown in the original solution.

4. Modifying Pointer Variables in Multiple Places

Incrementing or decrementing pointers in multiple places within the same iteration can lead to skipping elements or going out of bounds:

Incorrect Implementation:

while left < right:
    if nums[left] % 2 == 0:
        left += 1
    if nums[right] % 2 == 1:  # Should be 'elif', not 'if'
        right -= 1
    # This could move both pointers even when no swap occurs
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

Solution: Use if-elif-else structure to ensure only one action is taken per iteration, making the logic clear and preventing pointer manipulation errors.