Jobs

Interviews

Discussions

Sort an Array

Medium

Asked by:

More companies

152 views

Topics:

Arrays

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.

Constraints:

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

Try coding it in LeetCode

Sort an Array

Medium

Asked by:

More companies

152 views

Topics:

Arrays

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.

Constraints:

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

Try coding it in LeetCode

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 range of integer values within the input array? Could there be extremely large or small values?
Can the input array be empty or null?
Should the sorting algorithm be in-place, or am I allowed to use extra space to create a new sorted array?
Are there any memory constraints I should be aware of, given the potential size of the input?
Are there any constraints on the types of sorting algorithms I can use, or should I choose the most efficient one based on the input characteristics?

Brute Force Solution

Approach

The most straightforward way to sort is to explore all possible arrangements of the items. We check each arrangement to see if it's in the correct order. If it is, then we are done; if not, we try the next arrangement.

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

Consider all the different ways you could rearrange the items.
For each possible rearrangement, check if the items are now in the correct order.
If the items are in the correct order, you're finished!
If they are not, move on to the next possible rearrangement and repeat the check.
Continue this process until you find an arrangement where the items are sorted correctly.

Code Implementation

import itertools

def is_sorted(items):
    for i in range(len(items) - 1):
        if items[i] > items[i + 1]:
            return False
    return True

def sort_an_array(items_to_sort):
    # Generate all possible permutations of the input array
    all_permutations = itertools.permutations(items_to_sort)

    for possible_arrangement in all_permutations:
        # Check if this permutation is sorted.

        list_arrangement = list(possible_arrangement)
        if is_sorted(list_arrangement):
            # If a sorted arrangement is found, return it.

            return list_arrangement

    return list(items_to_sort)

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm explores all possible permutations of the input array of size n. There are n! (n factorial) possible permutations. For each permutation, the algorithm checks if the array is sorted, which requires comparing each element to its neighbor, taking O(n) time. Therefore, the total time complexity is O(n! * n), where n! represents generating each permutation, and n represents verifying if that permutation is sorted.

Space Complexity

O(N!) – The described algorithm explores all possible arrangements (permutations) of the input array. To generate these permutations, the algorithm implicitly uses a recursive approach or an iterative approach that stores intermediate permutations. In the worst-case scenario, it might need to store all N! permutations simultaneously or maintain a data structure to track the permutations being explored, which grows proportionally to N!. Therefore, the space complexity is directly related to the number of possible permutations of the array. Since it is exploring all possible permutations, the space required to keep track of those permutations grows factorially with the input size N.

Optimal Solution

Approach

The fastest way to sort is to divide the pile into smaller piles. Then, merge these piles together in a specific way to get a fully sorted result. This avoids unnecessary comparisons.

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

First, split the entire collection of items into smaller sub-collections until each sub-collection contains only one item (which is inherently sorted).
Next, repeatedly merge the sub-collections in pairs. When merging, compare the first item of each sub-collection and put the smaller one into a new, sorted collection.
Continue this comparison and merging process, always picking the smaller item and adding it to the new collection, until one of the sub-collections is empty.
Add any remaining items from the non-empty sub-collection to the end of the new, sorted collection.
Replace the original two sub-collections with this new, larger sorted collection.
Keep merging the collections until you are left with only one collection: the fully sorted set of items.

Code Implementation

def sort_array(input_array):
    if len(input_array) <= 1:
        return input_array

    def merge(left_subarray, right_subarray):
        merged_array = []
        left_index = 0
        right_index = 0

        # Compare elements from both subarrays and merge them.
        while left_index < len(left_subarray) and right_index < len(right_subarray):
            if left_subarray[left_index] < right_subarray[right_index]:
                merged_array.append(left_subarray[left_index])
                left_index += 1
            else:
                merged_array.append(right_subarray[right_index])
                right_index += 1

        # Add any remaining elements from the left subarray.
        while left_index < len(left_subarray):
            merged_array.append(left_subarray[left_index])
            left_index += 1

        # Add any remaining elements from the right subarray.
        while right_index < len(right_subarray):
            merged_array.append(right_subarray[right_index])
            right_index += 1

        return merged_array

    # Recursively split array into smaller subarrays.
    middle_index = len(input_array) // 2
    left_half = input_array[:middle_index]
    right_half = input_array[middle_index:]

    left_half = sort_array(left_half)
    right_half = sort_array(right_half)

    # Merge the sorted subarrays.
    return merge(left_half, right_half)

Big(O) Analysis

Time Complexity

O(n log n) – The merge sort algorithm operates in two phases. First, the array of size n is recursively divided into smaller sub-arrays until each contains only one element. This division process takes O(log n) time. Then, the algorithm repeatedly merges these sub-arrays in a sorted manner. Each merge operation compares and places elements, which takes O(n) time in the worst case for merging all the sub-arrays at each level. Since there are log n levels of merging, the total time complexity is O(n log n).

Space Complexity

O(N) – The merge sort algorithm, as described, repeatedly creates new, sorted sub-collections during the merging process. In the worst case, a temporary collection of size N (where N is the number of elements in the input array) is required to store the merged result before replacing the original sub-collections. Although the plain English explanation doesn't explicitly mention recursion, a typical merge sort implementation uses recursion, contributing O(log N) stack space. However, the temporary array of size N dominates, leading to O(N) auxiliary space.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on the requirements.
Array with one element	Return the array directly as it is already sorted.
Array with two elements that are out of order	A simple swap ensures the array is sorted in ascending order.
Large array exceeding available memory	Consider using an external merge sort or an in-place sorting algorithm that minimizes memory usage if necessary.
Array containing only duplicate values	The sorting algorithm should handle this without issues, resulting in an array of identical values.
Array containing a mix of positive, negative, and zero values	The sorting algorithm should correctly order the elements from negative to positive, with zero in the appropriate position.
Array with integer overflow potential during comparisons (only relevant for comparison-based sorts)	Use a safe comparison method to prevent integer overflow when comparing two elements.
Array with extremely large numbers (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Ensure the chosen sorting algorithm handles these boundary values correctly without causing issues like integer overflows during intermediate calculations (e.g., when calculating midpoints in merge sort).

Null or empty input array

How to Handle:

Return an empty array or throw an IllegalArgumentException, depending on the requirements.

Array with one element

How to Handle:

Return the array directly as it is already sorted.

Array with two elements that are out of order

How to Handle:

A simple swap ensures the array is sorted in ascending order.

Large array exceeding available memory

How to Handle:

Consider using an external merge sort or an in-place sorting algorithm that minimizes memory usage if necessary.

Array containing only duplicate values

How to Handle:

The sorting algorithm should handle this without issues, resulting in an array of identical values.

Array containing a mix of positive, negative, and zero values

How to Handle:

The sorting algorithm should correctly order the elements from negative to positive, with zero in the appropriate position.

Array with integer overflow potential during comparisons (only relevant for comparison-based sorts)

How to Handle:

Use a safe comparison method to prevent integer overflow when comparing two elements.

Array with extremely large numbers (close to Integer.MAX_VALUE or Integer.MIN_VALUE)

How to Handle:

Ensure the chosen sorting algorithm handles these boundary values correctly without causing issues like integer overflows during intermediate calculations (e.g., when calculating midpoints in merge sort).

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 range of integer values within the input array? Could there be extremely large or small values?
Can the input array be empty or null?
Should the sorting algorithm be in-place, or am I allowed to use extra space to create a new sorted array?
Are there any memory constraints I should be aware of, given the potential size of the input?
Are there any constraints on the types of sorting algorithms I can use, or should I choose the most efficient one based on the input characteristics?

Brute Force Solution

Approach

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

Consider all the different ways you could rearrange the items.
For each possible rearrangement, check if the items are now in the correct order.
If the items are in the correct order, you're finished!
If they are not, move on to the next possible rearrangement and repeat the check.
Continue this process until you find an arrangement where the items are sorted correctly.

Code Implementation

import itertools

def is_sorted(items):
    for i in range(len(items) - 1):
        if items[i] > items[i + 1]:
            return False
    return True

def sort_an_array(items_to_sort):
    # Generate all possible permutations of the input array
    all_permutations = itertools.permutations(items_to_sort)

    for possible_arrangement in all_permutations:
        # Check if this permutation is sorted.

        list_arrangement = list(possible_arrangement)
        if is_sorted(list_arrangement):
            # If a sorted arrangement is found, return it.

            return list_arrangement

    return list(items_to_sort)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The fastest way to sort is to divide the pile into smaller piles. Then, merge these piles together in a specific way to get a fully sorted result. This avoids unnecessary comparisons.

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

First, split the entire collection of items into smaller sub-collections until each sub-collection contains only one item (which is inherently sorted).
Next, repeatedly merge the sub-collections in pairs. When merging, compare the first item of each sub-collection and put the smaller one into a new, sorted collection.
Continue this comparison and merging process, always picking the smaller item and adding it to the new collection, until one of the sub-collections is empty.
Add any remaining items from the non-empty sub-collection to the end of the new, sorted collection.
Replace the original two sub-collections with this new, larger sorted collection.
Keep merging the collections until you are left with only one collection: the fully sorted set of items.

Code Implementation

def sort_array(input_array):
    if len(input_array) <= 1:
        return input_array

    def merge(left_subarray, right_subarray):
        merged_array = []
        left_index = 0
        right_index = 0

        # Compare elements from both subarrays and merge them.
        while left_index < len(left_subarray) and right_index < len(right_subarray):
            if left_subarray[left_index] < right_subarray[right_index]:
                merged_array.append(left_subarray[left_index])
                left_index += 1
            else:
                merged_array.append(right_subarray[right_index])
                right_index += 1

        # Add any remaining elements from the left subarray.
        while left_index < len(left_subarray):
            merged_array.append(left_subarray[left_index])
            left_index += 1

        # Add any remaining elements from the right subarray.
        while right_index < len(right_subarray):
            merged_array.append(right_subarray[right_index])
            right_index += 1

        return merged_array

    # Recursively split array into smaller subarrays.
    middle_index = len(input_array) // 2
    left_half = input_array[:middle_index]
    right_half = input_array[middle_index:]

    left_half = sort_array(left_half)
    right_half = sort_array(right_half)

    # Merge the sorted subarrays.
    return merge(left_half, right_half)

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 the requirements.
Array with one element	Return the array directly as it is already sorted.
Array with two elements that are out of order	A simple swap ensures the array is sorted in ascending order.
Large array exceeding available memory	Consider using an external merge sort or an in-place sorting algorithm that minimizes memory usage if necessary.
Array containing only duplicate values	The sorting algorithm should handle this without issues, resulting in an array of identical values.
Array containing a mix of positive, negative, and zero values	The sorting algorithm should correctly order the elements from negative to positive, with zero in the appropriate position.
Array with integer overflow potential during comparisons (only relevant for comparison-based sorts)	Use a safe comparison method to prevent integer overflow when comparing two elements.
Array with extremely large numbers (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Ensure the chosen sorting algorithm handles these boundary values correctly without causing issues like integer overflows during intermediate calculations (e.g., when calculating midpoints in merge sort).

Null or empty input array

How to Handle:

Return an empty array or throw an IllegalArgumentException, depending on the requirements.

Array with one element

How to Handle:

Return the array directly as it is already sorted.

Array with two elements that are out of order

How to Handle:

A simple swap ensures the array is sorted in ascending order.

Large array exceeding available memory

How to Handle:

Consider using an external merge sort or an in-place sorting algorithm that minimizes memory usage if necessary.

Array containing only duplicate values

How to Handle:

The sorting algorithm should handle this without issues, resulting in an array of identical values.

Array containing a mix of positive, negative, and zero values

How to Handle:

The sorting algorithm should correctly order the elements from negative to positive, with zero in the appropriate position.

Array with integer overflow potential during comparisons (only relevant for comparison-based sorts)

How to Handle:

Use a safe comparison method to prevent integer overflow when comparing two elements.

Array with extremely large numbers (close to Integer.MAX_VALUE or Integer.MIN_VALUE)

How to Handle: