2724. Sort By
Problem Description
In this problem, you are provided with two inputs: an array arr
which can contain any type of elements, and a function fn
which takes one of the elements of arr
as an argument and returns a number. The task is to sort the array arr
not by its actual values but by the numbers returned when each element is passed through the function fn
. The output should be a new array sortedArr
where the elements are ordered in ascending order based on the corresponding numbers returned from fn
. It is guaranteed that fn
will give a unique number for each element in the array, ensuring that there is a clear sort order.
Intuition
The given TypeScript function sortBy
takes in arr
and fn
and uses the sort
function to rearrange the elements in arr
. In TypeScript and JavaScript, the sort
function allows for a custom comparator, a function that takes in two elements and decides their order.
In this case, the comparator is ((a, b) => fn(a) - fn(b))
. This is a function that calls fn
on both elements a
and b
, subtracts the result of calling fn
on b
from the result of calling fn
on a
, and uses the result of the subtraction to determine their order:
- If
fn(a) - fn(b)
is less than 0,a
comes beforeb
in the sorted array. - If
fn(a) - fn(b)
is greater than 0,b
comes beforea
in the sorted array. - If
fn(a) - fn(b)
is 0 (which won't happen asfn
returns unique numbers),a
andb
would be considered equal in terms of sorting, but this scenario is excluded per the problem assumptions.
This use of the custom comparator in the sort
method achieves the goal of sorting the array by the values returned from the function fn
. Since arr.sort
sorts the elements of arr
in place and the comparator ensures it is in ascending order by fn
output, sortBy
returns the correctly sorted array.
Solution Approach
The implementation of the solution involves using the sort
method which is a built-in functionality of JavaScript and TypeScript arrays. This method sorts the elements of an array in place and can order them according to the return value of a provided function.
In our sortBy
function, we use arr.sort((a, b) => fn(a) - fn(b))
. Here's how it breaks down:
arr
: This is the array of elements we need to sort..sort()
: This method accepts a comparator function that determines the sort order.(a, b)
: The comparator function receives two elements from the array at a time.fn(a) - fn(b)
: Inside the comparator, we apply thefn
function to each elementa
andb
, then subtract the result ofb
froma
. The resulting number is used bysort
to determine their order.
Remember, the sort
method by default converts elements into strings and compares their sequences of UTF-16 code units values. However, when provided with a comparator function, it behaves as per the logic you provide in that function.
For the algorithms, data structures, or patterns used:
-
Algorithm: The specific sort algorithm used by
.sort()
is dependent on the JavaScript engine implementation. It could be quicksort, mergesort, or another algorithm optimized for different types of arrays and sizes. However, you don't need to know these specifics to use the method. -
Data Structures: Since we're sorting an array and not using any additional data structures, the only relevant data structure is the input array itself.
-
Patterns: A common programming pattern used here is the usage of higher-order functions.
fn
is a higher-order function since it takes a function as an argument (our comparator function) and returns a value based on the invocation of that function.
By using this approach, we get a sorted array based on the specified conditions using concise and effective code.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider arr
is an array of objects where each object has a name
and an age
property. We want to sort this array by the age of each person in ascending order.
const people = [
{ name: "Alice", age: 25 },
{ name: "Bob", age: 20 },
{ name: "Charlie", age: 30 }
];
function getAge(person) {
return person.age;
}
const sortedPeople = sortBy(people, getAge);
In the example above, our arr
is the people
array and our fn
is the getAge
function which extracts the age from an object.
Here's what happens step-by-step when our sortBy
function processes the people
array using the getAge
function as fn
:
- The
sortBy
function callsarr.sort((a,b) => fn(a) - fn(b))
, passing in our custom comparator. - The
sort
method begins to compare elements in the array using the comparator function:- It compares two elements of
people
, sayAlice
andBob
, by callinggetAge(Alice)
which returns 25 andgetAge(Bob)
which returns 20. - The computation
fn(a) - fn(b)
translates to25 - 20
, which is5
. Since the result is positive,Bob
will come beforeAlice
in the sorted array.
- It compares two elements of
- This process repeats for each pair of elements in the array, effectively organizing the entire
people
array according to the ages of the people in ascending order. - The
sortBy
function returns a new arraysortedPeople
:[ { name: "Bob", age: 20 }, { name: "Alice", age: 25 }, { name: "Charlie", age: 30 } ]
After the execution of sortBy
, the sortedPeople
array is sorted by the age
property. This walk-through illustrates the elegant and efficient use of the sort
method with a custom comparator function to sort objects by their specified properties.
Solution Implementation
1from typing import List, Callable
2
3def sort_by(array: List[T], comparator: Callable[[T], int]) -> List[T]:
4 """
5 Sorts an array based on a provided comparator function.
6
7 :param array: The array to be sorted.
8 :param comparator: A function that takes an item and returns a number,
9 representing that item's position in the sort order.
10 :return: The sorted array.
11 """
12
13 # Use the list's sort method by providing a lambda that calls
14 # the comparator function to determine the sort order.
15 # In Python, the sort method sorts the list in place.
16
17 array.sort(key=comparator)
18 return array
19
1import java.util.Collections;
2import java.util.Comparator;
3import java.util.List;
4
5/**
6 * Sorts a list based on a provided comparator function.
7 * @param <T> The type of elements in the list.
8 * @param list The list to be sorted.
9 * @param comparator A Comparator that compares two elements.
10 * @return The sorted list.
11 */
12public static <T> List<T> sortBy(List<T> list, Comparator<T> comparator) {
13 // Use the Collections.sort method, passing in the list and the comparator.
14 Collections.sort(list, comparator);
15 return list;
16}
17
1#include <vector>
2#include <algorithm>
3
4/**
5 * Sorts a vector based on a provided comparator function.
6 * @param array The vector to be sorted.
7 * @param comparator A function or functor that takes an item and returns a number,
8 * representing that item's position in the sort order.
9 * @returns The sorted vector.
10 */
11template<typename T>
12std::vector<T> sortBy(std::vector<T> array, const std::function<int(T)> &comparator) {
13 // Use the standard library's sort function, passing in a lambda that uses the
14 // comparator to determine the sort order.
15 std::sort(array.begin(), array.end(), [&comparator](const T &a, const T &b) {
16 return comparator(a) < comparator(b);
17 });
18 return array;
19}
20
1/**
2 * Sorts an array based on a provided comparator function.
3 * @param {T[]} array The array to be sorted.
4 * @param {(item: T) => number} comparator A function that takes an item and returns a number,
5 * representing that item's position in the sort order.
6 * @returns {T[]} The sorted array.
7 */
8function sortBy<T>(array: T[], comparator: (item: T) => number): T[] {
9 // Use the array sort function, passing in a lambda that uses the
10 // comparator to determine the sort order.
11 return array.sort((a, b) => comparator(a) - comparator(b));
12}
13
Time and Space Complexity
The time complexity of the sortBy
function largely depends on the implementation of the .sort()
method in JavaScript's V8 engine (used in Chrome and Node.js). This method generally uses the TimSort algorithm for arrays that have more than a certain number of elements, which has a time complexity of O(n log n)
on average and in the worst case. For smaller arrays, it may use an algorithm similar to insertion sort, which has a worst case time complexity of O(n^2)
.
The space complexity for TimSort is O(n)
. This is due to the need for allocating temporary arrays for storing merged sequences during the sorting process.
A key consideration here is the complexity of the fn
function that is being used to compare elements. If the complexity of this function is O(f(n))
, it should be multiplied by the sorting complexity. The overall time complexity would then become O(n log n * f(n))
for large arrays.
In summary:
- TimSort time complexity:
O(n log n)
- TimSort space complexity:
O(n)
- Overall time complexity (including
fn
):O(n log n * f(n))
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!