Sort By

This problem asks you to return a sorted array using a provided function that maps each element to a number. The sort must use these numbers to order elements ascendingly. Key insights include applying the function before sorting and handling non-primitive items correctly to avoid common pitfalls.

Problem Statement

Given an array arr and a function fn that maps each element to a number, return a new array sortedArr where elements are sorted in ascending order according to fn. You can assume fn returns unique numbers for the given array.

For example, if arr = [5, 4, 1, 2, 3] and fn = (x) => x, the sorted array should be [1, 2, 3, 4, 5]. Similarly, objects or nested arrays can be sorted using fn to extract the relevant numeric key or index.

Examples

Example 1

Input: arr = [5, 4, 1, 2, 3], fn = (x) => x

Output: [1, 2, 3, 4, 5]

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}]

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]]

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

Solution Approach

Precompute function outputs

Map each element of arr to a tuple of [fn(element), element] to ensure the sort is based on the function output while preserving original values. This prevents repeated fn calls during sorting.

Use built-in sort with custom comparator

Sort the mapped tuples using a comparator that compares the first element of each tuple. This guarantees ascending order according to fn and handles different data types consistently.

Extract sorted elements

After sorting, iterate over the tuples and collect the original elements in order. This produces the final sortedArr without altering the original elements or structure.

Complexity Analysis

Metric	Value
Time	O(NlogN)
Space	O(N)

Time complexity is O(NlogN) due to the sorting operation, and space complexity is O(N) to store the mapped tuples for stable sorting based on function outputs.

What Interviewers Usually Probe

• Check if the candidate precomputes fn values to avoid repeated computation during sort.
• Ask how the solution handles objects or nested arrays where fn extracts numeric keys or indices.
• Watch for candidates using unstable sorts or ignoring the ascending order requirement tied to fn.

Common Pitfalls or Variants

Common pitfalls

• Calling fn multiple times during sorting can increase runtime unnecessarily.
• Sorting the original array without preserving element references can break object or nested array structures.
• Assuming fn outputs are not unique may lead to incorrect handling of duplicates, even if the problem guarantees uniqueness.

Follow-up variants

• Sort descending by fn output instead of ascending, simply by reversing the comparator.
• Sort by multiple functions sequentially, applying a primary and secondary fn for tie-breaking.
• Handle arrays where fn may produce floating-point numbers, ensuring correct numeric sorting.

FAQ

What is the main idea behind the Sort By core interview pattern?

The pattern involves sorting elements of an array based on a function output, ensuring ascending order according to the function.

Can I use built-in sort functions for this problem?

Yes, built-in sort works efficiently when combined with a comparator that uses precomputed fn values.

How does GhostInterview handle objects or nested arrays in Sort By?

It extracts numeric keys or indices via fn and ensures the original elements are preserved after sorting.

What should I avoid when implementing Sort By?

Avoid calling fn repeatedly during sort, changing original element structures, or ignoring ascending order.

Is Sort By limited to numeric outputs from fn?

Yes, the problem assumes fn returns numbers which determine the ascending sort order of the array.