Sort Array By Parity II

The task is to sort an array in such a way that all the even integers are at even indices, and odd integers are at odd indices. Since we know that the array contains an equal number of even and odd numbers, we can achieve this using two pointers.

Approach

  1. Initialize Pointers: Create two pointers even and odd. Set even at the first even index (0) and odd at the first odd index (1).
  2. Partition Elements: Loop until even and odd are within the length of the array.
    • If the element at even index is even, increment even by 2.
    • If the element at odd index is odd, increment odd by 2.
    • If both conditions fail, it means nums[even] is odd and nums[odd] is even, so swap them, and increment both even and odd by 2.
  3. Return Result: The array will now have even elements at even indices and odd elements at odd indices.

Code

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

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        even, odd = 0, 1
        while even < len(nums) and odd < len(nums):
            if nums[even] % 2 == 0:
                even += 2
            elif nums[odd] % 2 == 1:
                odd += 2
            else:
                nums[even], nums[odd] = nums[odd], nums[even]
                even += 2
                odd += 2
        return nums

Example

  • Input: nums = [4,2,5,7]
  • Output: [4,5,2,7] (other valid outputs are also possible)
  • Explanation: Even numbers (4 and 2) are at even indices, and odd numbers (5 and 7) are at odd indices.

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.

title: Sort Array By Parity II tags: odd even linear-scan

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even. Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even. You may return any answer array that satisfies this condition.

Example 1:

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

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Discussion

0 1 2 3 4 5 6 7 [4,4,4,4,7,7,7,7] [4,4,4,7,4,7,7,7] [4,7,4,7,4,7,4,7] ^
^ 0 1 2 3 Input: [4,2,5,7] Output: [4,5,2,7] [2,7,4,5]

  1. Check if the number is odd, the index must also be odd and vice versa. 0 index is considered as even index.
  2. Sorting here does not really mean the elements are in ascending order.
  3. Iterate through the array.
    • Have two pointers, one for odd index and for even index.
    • Even pointer will put the elements in the even indices.
    • Odd pointer will put the elements in the odd indices.
  4. One pass sorting algorithm.
    • Start at index = 0 for even, for odd start from 0.
  5. Create an auxiliary array and put them into the correct index
  6. Invariant
    • Odd value in odd index, even value must be even index

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def sort_array_by_parity_ii(a)
  output = Array.new(a.size, 0) 
   
  index = 0
   
  for n in a
    if n.even?
      output[index] = n
      index += 2
    end
  end
   
  index = 1
  for n in a
    if n.odd?
      output[index] = n
      index += 2
    end
  end
 
  output
end

Time and Space Complexity

Time: O(n)
Space: O(n)

Refactored Solution

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

def sort_array_by_parity_ii(a)
  output = Array.new(a.size, 0)

  even_index = 0
  odd_index = 1

  for n in a
    if n.even?
      output[even_index] = n
      even_index += 2
    else
      output[odd_index] = n
      odd_index += 2        
    end
  end

  output
end

     0 1 2 3

Input: [4,2,5,7] Output: [4,5,2,7] [2,7,4,5]

  1. Check if the number is odd, the index must also be odd and vice versa 0 index is considered as even index

  2. Sorting here does not really mean the elements are in ascending order

  3. Iterate through the array Have two pointers, one for odd index and for even index Even pointer will put the elements in the even indices Odd pointer will put the elements in the odd indices

  4. One pass sorting algorithm Start at index = 0 for even, for odd start from 0,

  5. Create an auxiliary array and put them into the correct index

  6. Invariant

    • Odd value in odd index, even value must be even index
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# @param {Integer[]} a
# @return {Integer[]}
def sort_array_by_parity_ii(a)
    output = Array.new(a.size, 0)

    index = 0
    a.each_with_index do |n, i|
        if n.even?
            output[index] = n
            index += 2
        end
    end

    index = 1
    a.each_with_index do |n, i|
        if n.odd?
            output[index] = n
            index += 2
        end
    end

    return output
end