LeetCode 2724 - Sort By

LeetCode Problem 2724

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to sort an array using a custom sorting rule. Instead of sorting elements directly by their own value, we are given a function fn that transforms each element into a numeric value, and that numeric value determines the order.

In other words, every element in arr is assigned a sort key by calling fn(element). The array must then be reordered in ascending order according to those keys.

The input consists of two parts:

• arr, a valid JSON array containing any type of values, such as integers, objects, or nested arrays.
• fn, a function that takes one element from arr and returns a number.

The output should be a new ordering of arr, where elements are arranged in increasing order of the values returned by fn.

For example, if arr = [5, 4, 1, 2, 3] and fn(x) = x, the function simply returns the element itself. Since the sort key is the number, the result becomes [1, 2, 3, 4, 5].

In another example, if the array contains objects such as {"x": 1} and fn(d) = d.x, then sorting is based on the x field inside each object.

The constraints are important:

• 1 <= arr.length <= 5 * 10^5
• fn always returns a number
• fn will never return duplicate values for elements in the same array

The array size can be very large, up to 500,000 elements. This immediately tells us that inefficient sorting methods such as repeatedly scanning for the minimum element would be too slow. We need a solution that scales efficiently.

The guarantee that fn never returns duplicate numbers simplifies the problem because there are no ties to break. Every element has a unique ordering position.

Several edge cases are worth considering upfront. The array might already be sorted, completely reversed, contain only one element, contain objects or nested arrays instead of primitive values, or use negative numbers as sorting keys. Fortunately, because the problem guarantees unique numeric outputs from fn, we never need to worry about equal values creating ambiguity.

Approaches

Brute Force Approach

A straightforward but inefficient solution would be to repeatedly find the smallest remaining element according to fn.

The idea is simple. For every position in the result array:

1. Scan the entire remaining array.
2. Compute fn for every element.
3. Find the element with the smallest key.
4. Remove it and place it into the sorted result.

This produces the correct answer because each step greedily selects the smallest remaining element. Since the function outputs are unique, there is always exactly one valid smallest choice.

However, this approach is inefficient. If there are n elements, the first selection scans n elements, the second scans n - 1, and so on. This creates a total runtime of:

$$O(n + (n-1) + (n-2) + ... + 1) = O(n^2)$$

For n = 500,000, this would be far too slow.

Optimal Approach

The key observation is that this problem is fundamentally a sorting problem with a custom comparison key.

Most programming languages already provide optimized sorting algorithms. Instead of manually searching for the smallest element repeatedly, we can use the built-in sorting mechanism and provide fn as the key function.

The sorting algorithm internally compares elements using the values returned by fn. Since the outputs are guaranteed to be unique, the ordering is deterministic.

Modern sorting algorithms generally run in O(n log n) time, which is efficient enough for arrays containing hundreds of thousands of elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly finds the smallest remaining element
Optimal	O(n log n)	O(log n) to O(n)	Uses built-in sorting with fn as the key

Algorithm Walkthrough

Optimal Algorithm

1. Receive the input array arr and sorting function fn.

We are given a transformation function rather than direct comparison logic, so the first step is understanding that each element should be ordered according to fn(element). 2. Apply a sorting operation to the array.

Instead of implementing sorting manually, we use the language's built-in sorting functionality because it is already optimized for performance. 3. Use fn as the sorting key.

During sorting, the algorithm computes fn(element) for each element and compares those numeric outputs to determine ordering.

For example:

arr = [5, 4, 1, 2, 3]

fn(5) = 5
fn(4) = 4
fn(1) = 1
fn(2) = 2
fn(3) = 3

The sort order is determined by these numeric keys. 4. Return the sorted array.

After sorting completes, the array is already arranged in ascending order according to fn.

Why it works

The algorithm works because sorting by a key function guarantees that elements are ordered according to their transformed numeric values. Since fn produces unique numbers for every element, there is exactly one valid ascending ordering. The built-in sorting algorithm ensures that if fn(a) < fn(b), then a appears before b in the final result.

Python Solution

from typing import List, Callable, Any

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

The implementation is intentionally concise because Python provides a built-in sorted() function that directly supports custom sorting through the key parameter.

The sorted() function takes the original array and applies fn to every element to determine its sorting order. Internally, Python uses an efficient sorting algorithm, so we do not need to manually implement comparisons or swaps.

The expression key=fn tells Python to sort elements according to the numeric values returned by fn. Since the problem guarantees unique outputs, the resulting order is unambiguous.

The function returns a new sorted list rather than modifying the input array in place.

Go Solution

package main

import "sort"

func sortBy(arr []any, fn func(any) int) []any {
	sort.Slice(arr, func(i, j int) bool {
		return fn(arr[i]) < fn(arr[j])
	})

	return arr
}

In Go, there is no built-in equivalent to Python's sorted(..., key=...), so we use sort.Slice.

The sort.Slice function takes the array and a comparison function. Instead of providing a key directly, we compare two indices i and j and return whether arr[i] should come before arr[j].

The comparison uses:

fn(arr[i]) < fn(arr[j])

This ensures ascending order based on the numeric values returned by fn.

Unlike Python, Go sorts the slice in place, meaning the original array is modified and then returned.

Worked Examples

Example 1

Input:

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

Since fn(x) returns the element itself, sorting is based directly on the numbers.

Element	fn(element)
5	5
4	4
1	1
2	2
3	3

After sorting by these keys:

Sorted Key Order	Element
1	1
2	2
3	3
4	4
5	5

Output:

[1, 2, 3, 4, 5]

Example 2

Input:

arr = [{"x": 1}, {"x": 0}, {"x": -1}]
fn = (d) => d.x

We evaluate the sorting key for each object.

Object	fn(object)
{"x": 1}	1
{"x": 0}	0
{"x": -1}	-1

Sorting by ascending key:

Sorted Key Order	Object
-1	{"x": -1}
0	{"x": 0}
1	{"x": 1}

Output:

[{"x": -1}, {"x": 0}, {"x": 1}]

Example 3

Input:

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

The sorting key is the value at index 1.

Array	fn(array)
[3, 4]	4
[5, 2]	2
[10, 1]	1

Sorting by ascending key:

Sorted Key Order	Array
1	[10, 1]
2	[5, 2]
4	[3, 4]

Output:

[[10, 1], [5, 2], [3, 4]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Built-in sorting dominates runtime
Space	O(n)	Python's sorted() creates a new array

The time complexity comes from sorting n elements, which requires O(n log n) comparisons in efficient comparison-based sorting algorithms.

In Python, sorted() returns a new list, so additional memory proportional to the input size is required. In Go, sorting occurs in place, reducing auxiliary space usage, though internal recursion or bookkeeping may still require small extra memory.

Test Cases

solution = Solution()

# Example 1: simple integer sorting
assert solution.sortBy([5, 4, 1, 2, 3], lambda x: x) == [1, 2, 3, 4, 5]

# Example 2: sorting objects by field
assert solution.sortBy(
    [{"x": 1}, {"x": 0}, {"x": -1}],
    lambda d: d["x"]
) == [{"x": -1}, {"x": 0}, {"x": 1}]

# Example 3: sorting nested arrays by index
assert solution.sortBy(
    [[3, 4], [5, 2], [10, 1]],
    lambda x: x[1]
) == [[10, 1], [5, 2], [3, 4]]

# Single element array
assert solution.sortBy([42], lambda x: x) == [42]

# Already sorted input
assert solution.sortBy([1, 2, 3, 4], lambda x: x) == [1, 2, 3, 4]

# Reverse sorted input
assert solution.sortBy([5, 4, 3, 2, 1], lambda x: x) == [1, 2, 3, 4, 5]

# Negative numbers
assert solution.sortBy([-10, 5, -3, 2], lambda x: x) == [-10, -3, 2, 5]

# Sort by absolute value
assert solution.sortBy([-4, 2, -1, 7], lambda x: abs(x)) == [-1, 2, -4, 7]

# Large values
assert solution.sortBy([1000000, 5, 999999], lambda x: x) == [5, 999999, 1000000]

Test	Why
[5,4,1,2,3]	Verifies normal integer sorting
Object sorting by x	Ensures custom keys work on objects
Nested array sorting	Validates indexing-based keys
Single element	Tests minimum valid input size
Already sorted input	Ensures order remains correct
Reverse sorted input	Tests worst initial ordering
Negative numbers	Verifies handling of values below zero
Absolute value sorting	Confirms arbitrary custom key functions work
Large values	Ensures no assumptions about small numbers

Edge Cases

Single Element Array

The smallest valid input contains only one element. A naive implementation might accidentally fail due to assumptions about comparisons or indexing. In this implementation, sorting a one-element array simply returns that element unchanged because there is nothing to reorder.

Already Sorted Input

If the array is already arranged according to fn, the algorithm should leave it unchanged. Some manual implementations risk unnecessary modifications or unstable behavior. Since we rely on the language's built-in sorting algorithm, the order remains correct without additional work.

Complex Data Types

The array elements are not restricted to numbers. They may be objects, arrays, or mixed JSON-compatible structures. A buggy solution might incorrectly assume primitive numeric values. Our implementation avoids this problem because it never directly compares the elements themselves. Instead, it always compares the numeric result of fn.

Negative Sorting Keys

The function fn may return negative values. Incorrect implementations sometimes assume non-negative keys or use array indexing techniques that fail with negatives. Since sorting compares numbers directly, negative values are naturally handled and correctly placed before positive values.