Sort Array By Parity II Solution in Python

Problem Description

Welcome to the world of arrays, where even and odd numbers are like that couple at a party who just can’t seem to get along! The problem at hand, Sort Array By Parity II, is like trying to organize a dance floor where all the even-numbered guests are on one side and the odd-numbered guests are on the other.

Imagine you’re at a party, and you have a mix of friends who are either wearing blue (even numbers) or red (odd numbers). Your task is to make sure that every blue friend stands next to a red friend. Sounds simple, right? Well, it’s not as easy as it seems! You can’t just throw them together randomly; you have to follow the rules of parity!

The challenge is to rearrange the array so that every even index contains an even number and every odd index contains an odd number.

Code Solution


class Solution:
    def sortArrayByParityII(self, nums: list[int]) -> list[int]:
        n = len(nums)

        i = 0
        j = 1
        while i < n:
            while i < n and nums[i] % 2 == 0:
                i += 2
            while j < n and nums[j] % 2 == 1:
                j += 2
            if i < n:
                nums[i], nums[j] = nums[j], nums[i]

        return nums

Approach

The approach taken in this solution is quite straightforward. We use two pointers, i and j, to traverse the array. The pointer i starts at the first index (0) and moves through even indices, while j starts at the second index (1) and moves through odd indices.

If i points to an even number, it moves to the next even index.
If j points to an odd number, it moves to the next odd index.
If i points to an odd number and j points to an even number, we swap them.

This continues until we have traversed the entire array.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the input array. We traverse the array a constant number of times.
Space Complexity	O(1), as we are sorting the array in place without using any additional data structures.

Real-World Example

Think of a school dance where boys and girls must alternate in the line-up. If a boy (even number) is standing next to another boy, it’s a recipe for disaster! The teacher (our algorithm) goes through the line, ensuring that every boy is paired with a girl (odd number) next to him. By the end of the night, everyone is happily dancing in their proper places!