Leetcode 922 – Sort Array By Parity II – Python Code with Explanation

Summary of question

We are given an unsorted array of integers. Half of the integers are even while the other half are odd. Our goal is to sort the array in such a way that there is an even number at every even index of the array and an odd number at every odd index of the array.

Below is an example taken from Leetcode

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

In the output array, even indices 0 and 2 have even numbers while odd indices 1 and 3 have odd numbers.

Below are the constraints

• 2 <= nums.length <= 2 * 104
• nums.length is even.
• Half of the integers in nums are even.
• 0 <= nums[i] <= 1000

Link to Problem

https://leetcode.com/problems/sort-array-by-parity-ii/submissions/

Solution 1

In this solution, we will need to create a new array to store the result. Our Algorithm will be as follows

• Have two pointers, an even pointer starting at index 0 and an odd pointer starting at index1.
• Iterate over the input array. If an element is even,
  • add the element to our result array at index = even pointer.
  • Update value for even pointer, incrment it by 2 so that it points to the next even index

A similar logic has to be used for odd numbers in the input array.

Below is the code snippet

result_array = [0 for i in range(0,len(nums))] # Initialize result array
even_pointer = 0
odd_pointer = 1
for element in nums:
    if element % 2 == 0:
         result_array[even_pointer] = element
         even_pointer +=2
    else:
         result_array[odd_pointer] = element
         odd_pointer += 2
return result_array

Below are the stats for the above code submission

Runtime: 222 ms, faster than 20.28% of Python online submissions for Sort Array By Parity II.

Memory Usage: 15.5 MB, less than 46.16% of Python online submissions for Sort Array By Parity II.

Let’s try to come up with a better solution with respect to Memory Usage.

Solution 2

Instead of creating a new array, we will sort the array in place. We will basically have two pointers, an even pointer that iterates over even indices and an odd pointer that iterates over odd indices. Whenever an even pointer points to an odd element and the odd pointer points to an even element, we will swap the values.

The algorithm will be as follows

• Create two pointer variables even_pointer = 0 and odd_pointer = 1
• Iterate over input array and check if the element is even or odd
• If index is odd and element is odd
  • Increment value in odd_pointer by 2
• If index is even and element is even
  • Increment value in even_pointer by 2
• If even_pointer points to an odd element and odd_pointer points to an even element
  • Swap the values
  • Increment both pointers by 2

Below is the code snippet

even_pointer = 0 
odd_pointer = 1
length_nums = len(nums)
while (even_pointer < length_nums and odd_pointer < length_nums):
      if(nums[even_pointer] % 2 != 0 and nums[odd_pointer] % 2 == 0):
         nums[even_pointer] , nums[odd_pointer] = nums[odd_pointer], nums[even_pointer]
         even_pointer += 2
         odd_pointer += 2
      elif(nums[even_pointer]%2 == 0):
         even_pointer +=2
      elif(nums[odd_pointer]%2 !=0):
         odd_pointer +=2
return nums

The submissions stat is below

Runtime: 283 ms, faster than 13.09% of Python online submissions for Sort Array By Parity II.

Memory Usage: 15.1 MB, less than 94.00% of Python online submissions for Sort Array By Parity II.

Although this takes more time, we have reduced the space needed.