Skip to main content
Talentd

Sort By - Solution & Explanation

Easy7 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an array and a function fn. The task is to sort the array based on the value returned by applying fn to each element. Instead of comparing elements directly, you compare the computed keys produced by the function.

Approach 1: Using Built-in Sort with Key Function (Time: O(n log n), Space: O(1) to O(n))

The most direct solution relies on the language’s built-in sorting function. For each comparison, the algorithm applies fn(x) and fn(y) and orders the elements based on the returned values. Languages like Python provide a native key parameter, while JavaScript, Java, C++, and C# typically use a custom comparator that evaluates the function results during sorting.

The key idea is that the sorting algorithm handles ordering while your function defines the comparison rule. Internally, the algorithm performs O(n log n) comparisons, and each comparison may call the function. This makes the approach concise and easy to implement. For most interview scenarios and production code, this is the expected solution because it leverages optimized library sorting implementations.

This approach fits naturally into problems involving sorting and arrays, where you need to control ordering with a computed property.

Approach 2: Custom Sorting via a Map of Computed Keys (Time: O(n log n), Space: O(n))

Another option is to compute the key for every element once before sorting. Iterate through the array and store pairs like (fn(value), value) in a temporary structure such as a list or map. After that, sort the pairs using the precomputed key and extract the values in sorted order.

The key insight is avoiding repeated calls to fn. In some environments the sorting algorithm may evaluate the comparator many times, which can lead to redundant function executions. Precomputing the keys guarantees each element’s key is calculated exactly once. This pattern is sometimes called the “decorate-sort-undecorate” technique and commonly appears in custom comparator problems and hash map-based preprocessing.

The tradeoff is extra memory for storing the intermediate pairs. Time complexity remains O(n log n) because the array still needs to be sorted, but the function computation cost drops to O(n).

Recommended for interviews: The built-in sort with a key or comparator is what interviewers usually expect. It shows you understand how to customize sorting logic without reinventing the algorithm. Mentioning the precomputed-key optimization demonstrates deeper knowledge of how sorting repeatedly calls comparators and how to reduce redundant work.

Approach 1: Using Built-in Sort with Key Function

This approach utilizes the built-in sorting functionality available in most programming languages, which allows for custom sorting based on a key extracted from each element. The function fn is used to transform each element to its sorting key during the sort operation.

This solution makes use of Python's sorted() function, which accepts a key parameter. The key parameter is provided with the function fn, such that each element is processed through this function to determine the sorting order.

Code

PythonJavaScriptJavaC++C#

Python

JavaScript

Java

C++

C#

Complexity

Time Complexity: O(n log n), where n is the length of the array, due to the sort operation.
Space Complexity: O(n), as sorted() creates a new list.

Try this approach in the editor →

Approach 2: Using Custom Sorting via a Map of Computed Keys

This approach involves first creating a map of the computed keys from fn for all the elements in the array. These keys are then used to guide the sorting of the original array.

key_map stores the result of applying fn to each element. The array is sorted based on look-up from this dictionary during the sorting phase, providing a precomputed sort key per element.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n), owing to the sort operation.
Space Complexity: O(n), due to the additional storage in the form of key_map.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Built-in Sort with Key Function

Time Complexity: O(n log n), where n is the length of the array, due to the sort operation.
Space Complexity: O(n), as sorted() creates a new list.

Using Custom Sorting via a Map of Computed Keys

Time Complexity: O(n log n), owing to the sort operation.
Space Complexity: O(n), due to the additional storage in the form of key_map.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Built-in Sort with Key/ComparatorO(n log n)O(1) to O(n)Default solution in most languages; concise and uses optimized library sorting
Precompute Keys (Decorate-Sort-Undecorate)O(n log n)O(n)When the key function is expensive and you want to avoid repeated evaluations

Video Solution

Sort By | Leetcode 2724 | JSON | 30 Days of JavaScript #javascript #leetcode • Learn With Chirag • 1,652 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort By easy or hard?
Sort By is considered an easy problem because it mainly tests familiarity with built-in sorting APIs and comparator functions. The main idea is applying a function to derive the sorting key rather than comparing the raw values.
How to solve Sort By in O(n)?
Achieving O(n) time is generally not possible because the task requires sorting arbitrary values, which has a lower bound of O(n log n) for comparison-based algorithms. The best optimization is precomputing fn(x) for each element in O(n) and then sorting the precomputed pairs in O(n log n).
What is the best approach for Sort By?
The most practical solution uses the language's built-in sort with a key function or custom comparator. The sorting algorithm compares elements using fn(x) and fn(y) and orders them accordingly. This runs in O(n log n) time and requires little extra code while relying on highly optimized standard library implementations.
What data structure is used in Sort By?
The core structure is an array that gets sorted using a comparator or key function. Some implementations also use an auxiliary array or map to store precomputed key-value pairs before sorting.
What is the time complexity of Sort By?
Sorting dominates the runtime. Standard comparison-based sorting algorithms run in O(n log n) time. If the key function is evaluated during comparisons, it may be called multiple times, but the overall complexity still remains O(n log n).
Sort By Python or Java solution approach
In Python, the cleanest solution uses list.sort(key=fn) or sorted(arr, key=fn). In Java, C++, C#, and JavaScript, you typically pass a custom comparator to the sort function that compares fn(a) and fn(b). All implementations maintain O(n log n) time complexity.
Is Sort By asked at Google, Amazon, or Meta?
Problems involving custom sorting and comparator logic frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of sorting based on computed keys is a common interview concept.

Ready to solve this problem?

Practice Sort By with our built-in code editor and test cases.

Practice on FleetCode