Leetcode – Sort Array By Parity Solution in Python

Spread the love

The Sort Array By Parity problem on Leetcode is an engaging array manipulation problem that tests a programmer’s ability to efficiently reorganize elements based on specific criteria. In this comprehensive article, we’ll dissect the problem statement, explore various solution strategies, discuss Python implementations, and finally, delve into the time and space complexities of the proposed solutions.

Table of Contents:

  1. Understanding the Problem Statement
  2. Initial Approach: Two-pass Solution
  3. Two-pointer Approach
  4. In-place Reordering
  5. Python Implementations
  6. Complexity Analysis
  7. Conclusion

1. Understanding the Problem Statement

Problem:

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies the problem’s conditions.

Example:

Input: [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.

2. Initial Approach: Two-pass Solution

One of the most straightforward solutions is to iterate through the array twice. During the first iteration, collect all even numbers, and in the second iteration, collect all odd numbers.

Steps:

  1. Initialize two lists: evens and odds.
  2. Iterate through the array, adding even numbers to evens and odd numbers to odds.
  3. Merge the lists and return.

3. Two-pointer Approach

Another technique is to use two pointers, one starting at the beginning of the array and the other at the end. Repeatedly swap numbers until the two pointers meet.

Steps:

  1. Initialize two pointers: left at 0 and right at the last index.
  2. If the number at left is even, increment left.
  3. If the number at right is odd, decrement right.
  4. Otherwise, swap the numbers at left and right.

4. In-place Reordering

A variant of the two-pointer approach is to do in-place reordering without swapping.

Steps:

  1. Iterate through the array with a pointer i, placing even numbers at the beginning.
  2. Use another pointer j to keep track of the position where even numbers should be placed.

5. Python Implementations

Initial Approach:

def sortArrayByParity(A):
    evens = [x for x in A if x % 2 == 0]
    odds = [x for x in A if x % 2 == 1]
    return evens + odds

Two-pointer Approach:

def sortArrayByParity(A):
    left, right = 0, len(A) - 1
    while left < right:
        if A[left] % 2 > A[right] % 2:
            A[left], A[right] = A[right], A[left]
        if A[left] % 2 == 0:
            left += 1
        if A[right] % 2 == 1:
            right -= 1
    return A

In-place Reordering:

def sortArrayByParity(A):
    j = 0
    for i in range(len(A)):
        if A[i] % 2 == 0:
            A[i], A[j] = A[j], A[i]
            j += 1
    return A

6. Complexity Analysis

Initial Approach:

Time Complexity: O(n) – We iterate over the array twice.

Space Complexity: O(n) – We create two additional lists to store even and odd numbers.

Two-pointer Approach:

Time Complexity: O(n) – In the worst case, we might have to look at each element.

Space Complexity: O(1) – We do the sorting in-place without using extra space.

In-place Reordering:

Time Complexity: O(n) – We go through the array once.

Space Complexity: O(1) – No extra space other than the input array is used.

7. Conclusion

The Sort Array By Parity problem on Leetcode offers multiple angles of attack. While the initial two-pass solution is intuitive and straightforward, the two-pointer and in-place reordering techniques are more space-efficient and elegant.

Leave a Reply