Sort By

Difficulty: Easy | Acceptance: 83.10% | Paid: No Topics: N/A

Given an array arr and a function fn, return a sorted array sorted in ascending order by the results of running fn on each element of arr.

• Examples
• Constraints
• Built-in Sort with Custom Comparator
• Map-Sort-Map Pattern
• Bubble Sort

Examples

Example 1:

Input: arr = [5, 4, 1, 2, 3], fn = (x) => x
Output: [1, 2, 3, 4, 5]
Explanation: fn simply returns the value of the element 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 of the "x" key so the array is sorted by that value.

Example 3:

Input: arr = [[3, 4], [5, 2], [10, 1]], fn = (x) => x[1]
Output: [[10, 1], [5, 2], [3, 4]]
Explanation: fn returns the second element of each sub-array so the array is sorted by that value.

Constraints

- arr is a valid JSON array
- fn is a function that returns a number
- The returned values are unique
- 2 <= arr.length <= 5 * 10⁴

Built-in Sort with Custom Comparator

Intuition Use the language’s built-in sort function with a custom comparator that compares the values returned by fn for each element.

Steps

• Use the built-in sort function with a custom comparator
• The comparator compares fn(a) and fn(b) to determine the order
• Return the sorted array

from typing import List, Callable, Any

def sortBy(arr: List[Any], fn: Callable[[Any], int]) -> List[Any]:
    return sorted(arr, key=fn)

Complexity

• Time: O(n log n)
• Space: O(n) for creating a new array (or O(1) for in-place sort)
• Notes: This is the most efficient approach using built-in sorting algorithms.

Map-Sort-Map Pattern

Intuition Create pairs of (fn(value), value), sort by the fn(value), then extract the original values.

Steps

• Create an array of [fn(x), x] pairs for each element x in arr
• Sort the pairs based on the first element (fn(x))
• Extract and return the second element (x) from each sorted pair

from typing import List, Callable, Any

def sortBy(arr: List[Any], fn: Callable[[Any], int]) -> List[Any]:
    indexed = [(fn(x), x) for x in arr]
    indexed.sort(key=lambda p: p[0])
    return [x for _, x in indexed]

Complexity

• Time: O(n log n)
• Space: O(n) for storing the indexed pairs
• Notes: This pattern is useful when you need to sort by a computed value but preserve the original objects.

Bubble Sort

Intuition Implement bubble sort manually, comparing elements based on their fn values.

Steps

• Create a copy of the input array
• Repeatedly step through the array, comparing adjacent elements
• Swap elements if fn(arr[j]) > fn(arr[j+1])
• Continue until no swaps are needed

from typing import List, Callable, Any

def sortBy(arr: List[Any], fn: Callable[[Any], int]) -> List[Any]:
    result = arr[:]
    n = len(result)
    for i in range(n):
        for j in range(0, n - i - 1):
            if fn(result[j]) > fn(result[j + 1]):
                result[j], result[j + 1] = result[j + 1], result[j]
    return result

Complexity

• Time: O(n²)
• Space: O(n) for creating a copy of the array
• Notes: This approach is for educational purposes only. It is inefficient for large arrays compared to built-in sort.