Jobs

Interviews

Discussions

Sort Array By Parity

Easy

Amazon

1 view

Topics:

ArraysTwo Pointers

Given an integer array nums, move all the even integers to the beginning of the array, followed by all the odd integers. Return any array that satisfies this condition.

For example:

Input: nums = [3, 1, 2, 4]
Output: [2, 4, 3, 1] (Other valid outputs: [4, 2, 3, 1], [2, 4, 1, 3], and [4, 2, 1, 3]).
Input: nums = [0]
Output: [0]

Clarifications:

Can you modify the array in-place, or do I need to create a new array?
What should I return if the input array is null or empty?
What is the range of values in the integer array? Are there any negative numbers or other constraints?

Write a function to solve this problem with optimal time and space complexity.

Sort Array By Parity

Easy

Amazon

1 view

Topics:

ArraysTwo Pointers

Given an integer array nums, move all the even integers to the beginning of the array, followed by all the odd integers. Return any array that satisfies this condition.

For example:

Input: nums = [3, 1, 2, 4]
Output: [2, 4, 3, 1] (Other valid outputs: [4, 2, 3, 1], [2, 4, 1, 3], and [4, 2, 1, 3]).
Input: nums = [0]
Output: [0]

Clarifications:

Can you modify the array in-place, or do I need to create a new array?
What should I return if the input array is null or empty?
What is the range of values in the integer array? Are there any negative numbers or other constraints?

Write a function to solve this problem with optimal time and space complexity.

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:

Can the input array contain negative numbers or zeros?
Are there any constraints on the range of integer values within the array?
Are duplicate numbers allowed in the input array, and if so, does their relative ordering need to be preserved among even or odd numbers?
Should the sorting be done in-place, or am I allowed to return a new array?
Is there a specific order required for even numbers relative to each other or odd numbers relative to each other? If multiple solutions are valid, which should I prioritize?

Brute Force Solution

Approach

The brute force approach to sorting by parity means we explore all possible arrangements of the numbers. We check each arrangement to see if it satisfies the condition that even numbers come before odd numbers. If it does, we keep it; otherwise, we discard it.

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

Consider all possible orderings of the numbers in the list.
For each of these orderings, check if all the even numbers come before all the odd numbers.
If the even numbers come before the odd numbers, this ordering is a valid solution. Store this result.
After checking all possible orderings, choose any one of the valid solutions to give as the answer.

Code Implementation

import itertools

def sort_array_by_parity_brute_force(numbers):

    all_permutations = list(itertools.permutations(numbers))

    valid_solutions = []

    for permutation in all_permutations:
        # Check if the current permutation satisfies the parity condition.

        is_valid = True
        
        # Iterate through the permutation and check the parity.
        even_numbers_passed = False
        for number in permutation:
            if number % 2 == 0:
                if even_numbers_passed:
                    is_valid = False
                    break
            else:
                # Mark that we have passed even numbers.
                even_numbers_passed = True
        
        if is_valid:
            # Store the permutation if it's a valid solution.

            valid_solutions.append(list(permutation))
    
    # If there are any valid solutions, return the first one.
    if valid_solutions:
        return valid_solutions[0]
    else:
        return []

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach considers all possible permutations of the input array of size n. There are n! (n factorial) such permutations. For each permutation, the algorithm checks if all even numbers precede all odd numbers, which requires iterating through the array once, taking O(n) time. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N*N!) – The brute force approach considers all possible orderings of the N numbers in the input array. Each ordering requires storing a copy of the array, which takes O(N) space. Since there are N! possible orderings, and we might potentially store all valid solutions before picking one, the overall auxiliary space complexity becomes O(N * N!).

Optimal Solution

Approach

The goal is to rearrange numbers such that all even numbers appear before all odd numbers. The clever trick is to use two pointers, one at the beginning and one at the end, and swap numbers when they're out of order.

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

Imagine having two markers, one at the very start and another at the very end of the list of numbers.
Move the marker at the start towards the right until you find an odd number.
Move the marker at the end towards the left until you find an even number.
If the two markers have not crossed each other, it means you've found an odd number on the left side and an even number on the right side, so you swap them.
Keep doing this until the two markers meet or cross. At that point, all the even numbers will be on the left and all the odd numbers will be on the right.

Code Implementation

def sort_array_by_parity(numbers):
    start_index = 0
    end_index = len(numbers) - 1

    while start_index < end_index:
        # Find the first odd number from the left
        while start_index < end_index and numbers[start_index] % 2 == 0:
            start_index += 1

        # Find the first even number from the right
        while start_index < end_index and numbers[end_index] % 2 != 0:
            end_index -= 1

        # Swap if an odd number is on the left and an even on the right
        if start_index < end_index:
            numbers[start_index], numbers[end_index] = numbers[end_index], numbers[start_index]

            start_index += 1
            end_index -= 1

    return numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, one starting from the beginning and one from the end of the array. The while loop continues as long as the left pointer is less than the right pointer. Inside the loop, the left pointer moves right until it finds an odd number, and the right pointer moves left until it finds an even number. If they haven't crossed, the elements at these pointers are swapped. In the worst-case scenario, each pointer traverses the entire array once, resulting in a maximum of n comparisons and swaps. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses two pointers, one at the beginning and one at the end of the input array. These pointers occupy a constant amount of space, irrespective of the size N of the input array. No additional data structures like auxiliary arrays or hash maps are used. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return the input array immediately if null or empty, as there's nothing to sort.
Array with one element	Return the single-element array immediately, as it is already sorted by parity.
Array with all even numbers	The algorithm should correctly place all even numbers at the beginning, resulting in no changes.
Array with all odd numbers	The algorithm should correctly place all odd numbers at the end, resulting in a complete swap of elements.
Array with alternating even and odd numbers	The algorithm will perform swaps until all even numbers are at the front and odd numbers are at the back.
Array with large size (potential performance issue)	Ensure the algorithm used has a time complexity of O(n) or O(n log n) to avoid performance bottlenecks with large arrays; a two-pointer approach is optimal.
Array with negative even and odd numbers	The parity check should work correctly with negative numbers (e.g., num % 2 == 0 determines evenness).
Array containing zero values	Zero is considered even, so the algorithm should place zeros towards the beginning of the array.

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:

Can the input array contain negative numbers or zeros?
Are there any constraints on the range of integer values within the array?
Are duplicate numbers allowed in the input array, and if so, does their relative ordering need to be preserved among even or odd numbers?
Should the sorting be done in-place, or am I allowed to return a new array?
Is there a specific order required for even numbers relative to each other or odd numbers relative to each other? If multiple solutions are valid, which should I prioritize?

Brute Force Solution

Approach

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

Consider all possible orderings of the numbers in the list.
For each of these orderings, check if all the even numbers come before all the odd numbers.
If the even numbers come before the odd numbers, this ordering is a valid solution. Store this result.
After checking all possible orderings, choose any one of the valid solutions to give as the answer.

Code Implementation

import itertools

def sort_array_by_parity_brute_force(numbers):

    all_permutations = list(itertools.permutations(numbers))

    valid_solutions = []

    for permutation in all_permutations:
        # Check if the current permutation satisfies the parity condition.

        is_valid = True
        
        # Iterate through the permutation and check the parity.
        even_numbers_passed = False
        for number in permutation:
            if number % 2 == 0:
                if even_numbers_passed:
                    is_valid = False
                    break
            else:
                # Mark that we have passed even numbers.
                even_numbers_passed = True
        
        if is_valid:
            # Store the permutation if it's a valid solution.

            valid_solutions.append(list(permutation))
    
    # If there are any valid solutions, return the first one.
    if valid_solutions:
        return valid_solutions[0]
    else:
        return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine having two markers, one at the very start and another at the very end of the list of numbers.
Move the marker at the start towards the right until you find an odd number.
Move the marker at the end towards the left until you find an even number.
If the two markers have not crossed each other, it means you've found an odd number on the left side and an even number on the right side, so you swap them.
Keep doing this until the two markers meet or cross. At that point, all the even numbers will be on the left and all the odd numbers will be on the right.

Code Implementation

def sort_array_by_parity(numbers):
    start_index = 0
    end_index = len(numbers) - 1

    while start_index < end_index:
        # Find the first odd number from the left
        while start_index < end_index and numbers[start_index] % 2 == 0:
            start_index += 1

        # Find the first even number from the right
        while start_index < end_index and numbers[end_index] % 2 != 0:
            end_index -= 1

        # Swap if an odd number is on the left and an even on the right
        if start_index < end_index:
            numbers[start_index], numbers[end_index] = numbers[end_index], numbers[start_index]

            start_index += 1
            end_index -= 1

    return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return the input array immediately if null or empty, as there's nothing to sort.
Array with one element	Return the single-element array immediately, as it is already sorted by parity.
Array with all even numbers	The algorithm should correctly place all even numbers at the beginning, resulting in no changes.
Array with all odd numbers	The algorithm should correctly place all odd numbers at the end, resulting in a complete swap of elements.
Array with alternating even and odd numbers	The algorithm will perform swaps until all even numbers are at the front and odd numbers are at the back.
Array with large size (potential performance issue)	Ensure the algorithm used has a time complexity of O(n) or O(n log n) to avoid performance bottlenecks with large arrays; a two-pointer approach is optimal.
Array with negative even and odd numbers	The parity check should work correctly with negative numbers (e.g., num % 2 == 0 determines evenness).
Array containing zero values	Zero is considered even, so the algorithm should place zeros towards the beginning of the array.