Sort By

Problem Statement

Given an array named arr and a function fn, the task is to produce a new array sortedArr. The function fn takes an element of arr and returns a number, which dictates the order in which elements appear in sortedArr. Specifically, sortedArr must be sorted in ascending order based on the numbers returned by the function fn. Importantly, fn is guaranteed to produce unique output values for each element in the array arr, eliminating the possibility of duplicates influencing the sort order.

Examples

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 * 105

Approach and Intuition

The core of solving this problem involves understanding how sorting mechanisms can be customized with a function to determine the order. Here’s how you could think about approaching the problem:

1. Recognize that each element of arr will be associated with a unique number derived from applying fn.
2. Because fn consistently returns a unique number for different elements, the task simplifies to sorting these numbers.
3. Each number returned by fn acts as a sort key for its corresponding element in arr.
4. To achieve the solution:
   • Map each element of arr to its corresponding numeric key using fn.
   • Sort these key-element pairs by the numeric key.
   • Derive the sorted array from these sorted pairs.

By following this process, you can sort an array based on almost any criteria provided by a function, as long as it adheres to the rules set (i.e., returning a unique number for each element). This provides a powerful way to customize sorting orders beyond traditional ascending or descending sort of native array elements.

Solutions

var sortArray = function(list, transform) {
    function compare(first, second) {
        return (transform(first) < transform(second)) ? -1 : 1;
    }
    
    return list.sort(compare);
};