How do you solve Sort Array By Parity II on LeetCode?

Sort Array By Parity II (LeetCode #922) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The problem requires maintaining the parity of numbers at specific indices.

What is the brute force solution for Sort Array By Parity II?

The brute force approach for Sort Array By Parity II is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves creating two separate lists for even and odd numbers and then merging them back into the original array. This is simple but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Sort Array By Parity II?

Sort Array By Parity II uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Two Pointers, Array.

What are the interview tips for Sort Array By Parity II?

Always clarify constraints and edge cases with the interviewer. Explain your thought process while coding, as it shows your understanding. Consider space and time complexity early to guide your approach.

What are common mistakes when solving Sort Array By Parity II?

Not recognizing that the array length is even, which simplifies the problem. Failing to swap correctly when both pointers point to incorrect values.

#922

Sort Array By Parity II

Easy

ArrayTwo PointersSortingTwo PointersArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a two-pointer technique to place even and odd numbers directly in their correct positions without using extra space for lists.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers: one for even indices (i = 0) and one for odd indices (j = 1).
2Step 2: While both pointers are within the array bounds, check if the number at the even index is even and the number at the odd index is odd.
3Step 3: If both are correct, move both pointers forward. If not, swap the numbers at the two pointers and adjust accordingly.

solution.py12 lines

1# Full working Python code
2
3def sortArrayByParityII(nums):
4    i, j = 0, 1
5    while i < len(nums) and j < len(nums):
6        if nums[i] % 2 == 0:
7            i += 2
8        elif nums[j] % 2 == 1:
9            j += 2
10        else:
11            nums[i], nums[j] = nums[j], nums[i]
12    return nums

ℹ

Complexity note: The time complexity is O(n) because we traverse the array only once. The space complexity is O(1) since we are not using any extra space besides a few variables.

1The problem requires maintaining the parity of numbers at specific indices.
2Using a two-pointer technique allows for in-place sorting without extra space.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.