Sort By

#673 Most AskedEasy

Sort By #673 Most Asked

Easy

2 views

Topics:

Arrays

Given an array arr and a function fn, return a sorted array sortedArr. You can assume fn only returns numbers and those numbers determine the sort order of sortedArr. sortedArr must be sorted in ascending order by fn output.

You may assume that fn will never duplicate numbers for a given array.

Example 1:

Input: arr = [5, 4, 1, 2, 3], fn = (x) => x
Output: [1, 2, 3, 4, 5]
Explanation: fn simply returns the number passed to it so the array is sorted in ascending order.

Example 2:

Input: arr = [{"x": 1}, {"x": 0}, {"x": -1}], fn = (d) => d.x
Output: [{"x": -1}, {"x": 0}, {"x": 1}]
Explanation: fn returns the value for the "x" key. So the array is sorted based on that value.

Example 3:

Input: arr = [[3, 4], [5, 2], [10, 1]], fn = (x) => x[1]
Output: [[10, 1], [5, 2], [3, 4]]
Explanation: arr is sorted in ascending order by number at index=1.

Constraints:

arr is a valid JSON array
fn is a function that returns a number
1 <= arr.length <= 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 data type of the elements to be sorted, and are there any restrictions on the range of values?
Can the input array be empty or contain null values?
Are we sorting in ascending or descending order by default?
If the custom sorting criteria results in a tie, how should I handle it?
Can you provide an example of the input array and the expected output after sorting?

Brute Force Solution

Approach

The brute force approach to sorting by a specific criteria involves checking every possible arrangement. It’s like trying every single ordering until you find the one that satisfies the sort requirements. This method guarantees finding the correct order but may take a very long time.

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

Consider all possible arrangements of the items you want to sort.
For each arrangement, check if it is correctly sorted according to the specified criteria.
If the arrangement is sorted correctly, you've found the solution.
If it's not sorted correctly, discard it and move on to the next possible arrangement.
Repeat this process until you find a correctly sorted arrangement.

Code Implementation

import itertools

def brute_force_sort(items, comparison_function):
    # Generate all possible permutations of the input items
    all_permutations = itertools.permutations(items)

    for possible_permutation in all_permutations:
        # Check if the current permutation is sorted according to comparison_function
        is_sorted = True
        for index in range(len(possible_permutation) - 1):

            if not comparison_function(possible_permutation[index], possible_permutation[index + 1]):
                is_sorted = False
                break

        # If a sorted permutation is found, return it
        if is_sorted:
            return list(possible_permutation)

    return list(items)

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 needs to verify if it's correctly sorted according to the given criteria. Checking if a permutation is sorted requires comparing adjacent elements, which takes O(n) time. Therefore, the overall time complexity is O(n! * n), as we generate each of the n! permutations and then spend O(n) time verifying the permutation.

Space Complexity

O(N) – The brute force approach considers all possible arrangements of the input items. To generate and store each arrangement, it requires auxiliary space proportional to the number of items being sorted, denoted as N. This is because each arrangement represents a permutation of the original input. Therefore, the space complexity is directly related to the size of the input, requiring an auxiliary array (or similar data structure) to hold a possible arrangement of size N.

Optimal Solution

Approach

The problem requires arranging a collection of items based on multiple criteria. We use a structured way to compare items, first by the primary criterion, and then by secondary criteria if the primary criterion is the same. This ensures a consistent and logical arrangement.

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

Understand the primary and secondary criteria for ordering the items.
Compare two items based on the primary criterion. If they are different, the item with the 'smaller' value according to the primary criteria is considered smaller.
If the primary criteria are the same, compare the items based on the secondary criteria. The item with the 'smaller' value according to the secondary criteria is then considered smaller.
Continue this comparison process for all pairs of items.
Use a sorting algorithm to arrange the items from smallest to largest, based on the pairwise comparison rules you established.

Code Implementation

def sort_by_multiple_criteria(items, primary_criteria, secondary_criteria):
    def compare_items(item1, item2):
        # Compare based on primary criteria first
        primary_comparison = primary_criteria(item1, item2)
        if primary_comparison != 0:
            return primary_comparison

        # If primary criteria are the same, compare by secondary
        return secondary_criteria(item1, item2)

    # Sort using the custom comparison function
    sorted_items = sorted(items, key=cmp_to_key(compare_items))
    return sorted_items

from functools import cmp_to_key

Big(O) Analysis

Time Complexity

O(n log n) – The solution describes a comparison-based sorting algorithm. Common efficient sorting algorithms like merge sort, heap sort, or a well-implemented quicksort achieve an average time complexity of O(n log n). The comparison logic within the sort function, which compares elements based on primary and secondary criteria, takes constant time, O(1). Therefore, the overall time complexity is dominated by the sorting algorithm itself, resulting in O(n log n).

Space Complexity

O(1) – The provided explanation focuses on comparisons between items and sorting based on defined criteria. It does not explicitly mention creation of any auxiliary data structures like temporary lists, hash maps, or recursion. The comparison process inherently works in place without requiring significant additional memory. Therefore, the auxiliary space complexity is constant, independent of the input size N.

Edge Cases

Case	How to Handle
Null or empty input list	Return an empty list or raise an IllegalArgumentException as the problem statement may allow or disallow
List with one or two elements	Handle trivially based on the specific sorting criteria; a list with one element is already sorted.
List contains only identical elements	The sorting criteria should determine the output, but ensure stability is maintained if required.
List contains very large numbers of elements (approaching memory limits)	Select an efficient sorting algorithm (e.g., merge sort or quick sort) and consider in-place sorting to minimize memory usage.
The comparison function may throw an error	Catch and handle any exceptions that arise during comparison to prevent program termination.
The comparison function is not transitive (a < b, b < c, but a > c)	The sorting algorithm may not converge or produce a correct result; document this limitation.
List contains a mix of different data types or uncomparable elements (if allowed by the language)	Handle type errors gracefully, either by raising an exception or filtering out incompatible elements before sorting.
Integer overflow during comparison if comparator does subtraction	Use subtraction only if it is safe, or use comparison operators that do not involve subtraction if applicable.

Null or empty input list

How to Handle:

Return an empty list or raise an IllegalArgumentException as the problem statement may allow or disallow

List with one or two elements

How to Handle:

Handle trivially based on the specific sorting criteria; a list with one element is already sorted.

List contains only identical elements

How to Handle:

The sorting criteria should determine the output, but ensure stability is maintained if required.

List contains very large numbers of elements (approaching memory limits)

How to Handle:

Select an efficient sorting algorithm (e.g., merge sort or quick sort) and consider in-place sorting to minimize memory usage.

The comparison function may throw an error

How to Handle:

Catch and handle any exceptions that arise during comparison to prevent program termination.

The comparison function is not transitive (a < b, b < c, but a > c)

How to Handle:

The sorting algorithm may not converge or produce a correct result; document this limitation.

List contains a mix of different data types or uncomparable elements (if allowed by the language)

How to Handle:

Handle type errors gracefully, either by raising an exception or filtering out incompatible elements before sorting.

Integer overflow during comparison if comparator does subtraction

How to Handle:

Use subtraction only if it is safe, or use comparison operators that do not involve subtraction if applicable.