Jobs

Interviews

Discussions

Sort Array By Parity II

Easy

Google

3 views

Topics:

ArraysTwo Pointers

You are given an array of integers nums where half of the integers are odd and the other half are even.

Your task is to sort the array such that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any array that satisfies this condition.

For example:

If nums = [4, 2, 5, 7], a possible output is [4, 5, 2, 7]. Other valid outputs include [4, 7, 2, 5] and [2, 5, 4, 7]. The key is that even numbers are at even indices and odd numbers are at odd indices.
If nums = [2, 3], the output should be [2, 3].

Constraints:

The length of nums is between 2 and 2 * 10^4.
The length of nums is even.
Half of the integers in nums are even.
Each element nums[i] is between 0 and 1000.

Could you describe an algorithm to solve this problem efficiently? What is the time and space complexity of your solution?

Sort Array By Parity II

Easy

Google

3 views

Topics:

ArraysTwo Pointers

You are given an array of integers nums where half of the integers are odd and the other half are even.

Your task is to sort the array such that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any array that satisfies this condition.

For example:

If nums = [4, 2, 5, 7], a possible output is [4, 5, 2, 7]. Other valid outputs include [4, 7, 2, 5] and [2, 5, 4, 7]. The key is that even numbers are at even indices and odd numbers are at odd indices.
If nums = [2, 3], the output should be [2, 3].

Constraints:

The length of nums is between 2 and 2 * 10^4.
The length of nums is even.
Half of the integers in nums are even.
Each element nums[i] is between 0 and 1000.

Could you describe an algorithm to solve this problem efficiently? What is the time and space complexity of your solution?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values within the input array?
Is the input array guaranteed to have an even length, and that exactly half the elements are even and half are odd?
If there are multiple possible sorted arrays that satisfy the parity condition, is any specific ordering preferred?
Can the input array contain zero?
Is it acceptable to modify the input array in place, or should I return a new array?

Brute Force Solution

Approach

The brute force way to sort an array by parity II is like trying every single possible arrangement. We'll check each arrangement to see if it meets the 'even number in even spot, odd number in odd spot' rule.

Here's how the algorithm would work step-by-step:

Consider every possible order the numbers in the array could be in.
For each of these arrangements, go through the array.
Check if every even number is in an even-numbered position and every odd number is in an odd-numbered position.
If the arrangement follows these rules, we've found a correct solution and we can stop.
If we've checked every possible arrangement and none of them are correct, then something went wrong (but for this question there should always be at least one solution).

Code Implementation

import itertools

def sort_array_by_parity_ii_brute_force(numbers):

    # Generate all possible permutations of the input array
    for permutation in itertools.permutations(numbers):

        is_valid_permutation = True

        # Check if the current permutation satisfies the parity condition
        for index, number in enumerate(permutation):

            #Verify if the number and index have the same parity
            if (index % 2 == 0 and number % 2 != 0) or \
               (index % 2 != 0 and number % 2 == 0):

                is_valid_permutation = False
                break

        #If valid return converted to list
        if is_valid_permutation:
            return list(permutation)

    return [] # Return empty list if no valid permutation is found

Big(O) Analysis

Time Complexity

O(n * n!) – The brute force approach considers every possible permutation of the array. Generating all permutations of an array of size n takes O(n!) time. For each permutation, we iterate through the entire array of size n to check if it satisfies the parity condition (even numbers at even indices and odd numbers at odd indices). Therefore, the overall time complexity is O(n * n!).

Space Complexity

O(N) – The described brute force approach involves generating and checking every possible permutation of the input array of size N. Although not explicitly stated, generating permutations often requires storing a copy of the array to manipulate, resulting in an auxiliary array of size N for each permutation. While the algorithm conceptually checks each permutation in place, a practical implementation would likely create a copy to avoid altering the original input array during the permutation process. Therefore, the space complexity is dominated by the temporary storage for each permutation, leading to O(N) auxiliary space.

Optimal Solution

Approach

The key idea is to directly place numbers into their correct positions based on whether they are even or odd. We use two pointers to efficiently find numbers that are out of place and swap them to fix the array without needing to sort it fully.

Here's how the algorithm would work step-by-step:

Imagine two people are walking through the list, one looking for even numbers in odd spots, and the other looking for odd numbers in even spots.
If the first person finds an even number in an odd spot, and the second person finds an odd number in an even spot, simply swap those two numbers.
Keep having the two people walk and swap until they reach the end of the list. At that point, every number will be in its correct spot based on whether it's even or odd.

Code Implementation

def sort_array_by_parity_ii(numbers):
    even_index = 0
    odd_index = 1

    # Iterate until either pointer reaches the end of the array.
    while even_index < len(numbers) and odd_index < len(numbers):

        # Find an even number at an odd index.
        while even_index < len(numbers) and numbers[even_index] % 2 == 0:
            even_index += 2

        # Find an odd number at an even index.
        while odd_index < len(numbers) and numbers[odd_index] % 2 != 0:
            odd_index += 2

        # If both pointers are still within bounds, swap the elements.
        if even_index < len(numbers) and odd_index < len(numbers):

            # Swap to put numbers in correct parity positions.
            numbers[even_index], numbers[odd_index] = numbers[odd_index], numbers[even_index]
            even_index += 2
            odd_index += 2

    return numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array using two pointers, one to find even numbers at odd indices and the other to find odd numbers at even indices. Each pointer traverses the array at most once. When both pointers find misplaced numbers, a swap is performed, and the pointers continue their traversal. Since the pointers move linearly through the array, the number of operations is proportional to the size of the input array, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm operates directly on the input array, modifying it in-place. It only uses two integer pointers to keep track of the positions of even and odd numbers that need to be swapped. The space required for these pointers remains constant irrespective of the size (N) of the input array, resulting in constant auxiliary space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on requirements.
Input array with an odd number of elements	Throw an IllegalArgumentException as the problem requires an even number of elements.
Input array where the number of even elements doesn't equal the number of odd elements	Throw an IllegalArgumentException since a valid solution is impossible.
Array contains only even numbers	The algorithm should still correctly place even numbers in even indices and odd numbers in odd indices assuming appropriate pre-validation for balanced parity.
Array contains only odd numbers	The algorithm should still correctly place even numbers in even indices and odd numbers in odd indices assuming appropriate pre-validation for balanced parity.
Array with a very large number of elements (potential performance bottleneck)	The chosen algorithm (e.g., two-pointer approach) should have a time complexity of O(n) to handle large inputs efficiently.
Integer overflow when dealing with extremely large numbers	The parity check (num % 2) should work correctly regardless of the size of the integer within the language's limits.
Input array contains negative numbers	The parity check (num % 2) should function correctly for negative numbers, distinguishing between even and odd.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values within the input array?
Is the input array guaranteed to have an even length, and that exactly half the elements are even and half are odd?
If there are multiple possible sorted arrays that satisfy the parity condition, is any specific ordering preferred?
Can the input array contain zero?
Is it acceptable to modify the input array in place, or should I return a new array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible order the numbers in the array could be in.
For each of these arrangements, go through the array.
Check if every even number is in an even-numbered position and every odd number is in an odd-numbered position.
If the arrangement follows these rules, we've found a correct solution and we can stop.
If we've checked every possible arrangement and none of them are correct, then something went wrong (but for this question there should always be at least one solution).

Code Implementation

import itertools

def sort_array_by_parity_ii_brute_force(numbers):

    # Generate all possible permutations of the input array
    for permutation in itertools.permutations(numbers):

        is_valid_permutation = True

        # Check if the current permutation satisfies the parity condition
        for index, number in enumerate(permutation):

            #Verify if the number and index have the same parity
            if (index % 2 == 0 and number % 2 != 0) or \
               (index % 2 != 0 and number % 2 == 0):

                is_valid_permutation = False
                break

        #If valid return converted to list
        if is_valid_permutation:
            return list(permutation)

    return [] # Return empty list if no valid permutation is found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two people are walking through the list, one looking for even numbers in odd spots, and the other looking for odd numbers in even spots.
If the first person finds an even number in an odd spot, and the second person finds an odd number in an even spot, simply swap those two numbers.
Keep having the two people walk and swap until they reach the end of the list. At that point, every number will be in its correct spot based on whether it's even or odd.

Code Implementation

def sort_array_by_parity_ii(numbers):
    even_index = 0
    odd_index = 1

    # Iterate until either pointer reaches the end of the array.
    while even_index < len(numbers) and odd_index < len(numbers):

        # Find an even number at an odd index.
        while even_index < len(numbers) and numbers[even_index] % 2 == 0:
            even_index += 2

        # Find an odd number at an even index.
        while odd_index < len(numbers) and numbers[odd_index] % 2 != 0:
            odd_index += 2

        # If both pointers are still within bounds, swap the elements.
        if even_index < len(numbers) and odd_index < len(numbers):

            # Swap to put numbers in correct parity positions.
            numbers[even_index], numbers[odd_index] = numbers[odd_index], numbers[even_index]
            even_index += 2
            odd_index += 2

    return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on requirements.
Input array with an odd number of elements	Throw an IllegalArgumentException as the problem requires an even number of elements.
Input array where the number of even elements doesn't equal the number of odd elements	Throw an IllegalArgumentException since a valid solution is impossible.
Array contains only even numbers	The algorithm should still correctly place even numbers in even indices and odd numbers in odd indices assuming appropriate pre-validation for balanced parity.
Array contains only odd numbers	The algorithm should still correctly place even numbers in even indices and odd numbers in odd indices assuming appropriate pre-validation for balanced parity.
Array with a very large number of elements (potential performance bottleneck)	The chosen algorithm (e.g., two-pointer approach) should have a time complexity of O(n) to handle large inputs efficiently.
Integer overflow when dealing with extremely large numbers	The parity check (num % 2) should work correctly regardless of the size of the integer within the language's limits.
Input array contains negative numbers	The parity check (num % 2) should function correctly for negative numbers, distinguishing between even and odd.