Sort Array By Parity

tags: odd even modulo

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 this condition.

Example 1:
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.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# @param {Integer[]} a
# @return {Integer[]}
def sort_array_by_parity(a)
  even = []
  odd = []
    
  a.each do |n|
    if n % 2 == 0
      even << n
    else
      odd << n
    end
  end
  
  even + odd
end

The task is to sort an array in such a way that all the even integers come first followed by all the odd integers. There are many ways to achieve this, and any valid sorting is acceptable. Here’s one way to do it:

Approach:

  1. Initialize Pointers: Create two pointers i and j. Set i at the beginning of the array and j at the end of the array.
  2. Partition Elements: Loop until i is less than j.
    • If nums[i] is odd and nums[j] is even, swap them.
    • If nums[i] is even, increment i.
    • If nums[j] is odd, decrement j.
  3. Return Result: The array will now have even elements at the beginning and odd elements at the end.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] % 2 > nums[j] % 2:
                nums[i], nums[j] = nums[j], nums[i]
            if nums[i] % 2 == 0:
                i += 1
            if nums[j] % 2 == 1:
                j -= 1
        return nums

Example:

  • Input: nums = [3,1,2,4]
  • Output: [2,4,3,1] (other valid outputs are also possible)
  • Explanation: Even numbers (2 and 4) are moved to the beginning, and odd numbers (3 and 1) are at the end.

Insights:

  • Time Complexity: The time complexity is (O(n)), where (n) is the length of the array. The algorithm scans the array once.
  • Space Complexity: The space complexity is (O(1)), as the sorting is done in place, and no additional space is used.
  • In-Place Sorting: This solution sorts the original array in place, achieving a space-efficient solution.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# @param {Integer[]} a
# @return {Integer[]}
def sort_array_by_parity(a)
    even = []
    odd = []

    a.each do |n|
       if n % 2 == 0
           even << n
       else
           odd << n
       end
    end
    even + odd
end