Sort By - Practice Coding Problems

Sort By - Problem

JavaScript Easy

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.

Input & Output

Example 1 — Basic Sorting

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

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

💡 Note: Function returns the number itself, so we sort in ascending order: 1 < 2 < 3 < 4 < 5

Example 2 — Custom Function

$ Input: arr = [5, 4, 1, 2, 3], fn = x => x * x

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

💡 Note: Sort by squares: fn(1)=1, fn(2)=4, fn(3)=9, fn(4)=16, fn(5)=25. Still ascending order.

Example 3 — Reverse Effect

$ Input: arr = [2, 3, 1, 4], fn = x => -x

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

💡 Note: Sort by negative values: fn(4)=-4, fn(3)=-3, fn(2)=-2, fn(1)=-1. Ascending by fn gives [4,3,2,1].

Constraints

1 ≤ arr.length ≤ 1000
-1000 ≤ arr[i] ≤ 1000
fn returns a number for every arr[i]
fn will not return duplicate numbers for a given array

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,4,1,2,3] with function fn(x) = x²

Transform

Calculate fn for each: [25,16,1,4,9]

Sort

Sort by fn values: [1,4,9,16,25] → [1,2,3,4,5]

Key Takeaway

🎯 Key Insight: Sort elements by their transformed values, not their original values

Asked in

G Google 42 a Amazon 38 M Microsoft 31 🍎 Apple 25

The key insight is to avoid recalculating function values during sorting. The optimal approach transforms all elements once, creating pairs of (value, fn_result), then sorts by fn_result. This reduces function calls from O(n² log n) to O(n). Best approach: Transform-then-sort with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Transform Then Sort	O(n log n)	O(n)	Calculate all function values once, then sort using built-in algorithm
Brute Force Bubble Sort	O(n²)	O(1)	Calculate function values and use bubble sort with custom comparison

Transform Then Sort — Algorithm Steps

Step 1: Create (value, fn_result) pairs
Step 2: Sort pairs by fn_result
Step 3: Extract sorted values

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Calculate fn(x) for each element once

Pair

Create (value, fn_result) pairs

Sort

Sort pairs by fn_result, extract values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int fnResult;
} Pair;

int parseFn(int x, char* fnStr) {
    if (strstr(fnStr, "+") != NULL) {
        char* plus = strstr(fnStr, "+");
        int val = atoi(plus + 1);
        return x + val;
    } else if (strstr(fnStr, "*") != NULL) {
        char* mult = strstr(fnStr, "*");
        int val = atoi(mult + 1);
        return x * val;
    }
    return x;
}

int comparePairs(const void* a, const void* b) {
    Pair* pairA = (Pair*)a;
    Pair* pairB = (Pair*)b;
    return pairA->fnResult - pairB->fnResult;
}

int* solution(int* arr, int size, char* fnStr) {
    // Create pairs of (original_value, function_result)
    Pair* pairs = (Pair*)malloc(size * sizeof(Pair));
    for (int i = 0; i < size; i++) {
        pairs[i].value = arr[i];
        pairs[i].fnResult = parseFn(arr[i], fnStr);
    }
    
    // Sort pairs by function result
    qsort(pairs, size, sizeof(Pair), comparePairs);
    
    // Extract original values in sorted order
    int* result = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        result[i] = pairs[i].value;
    }
    
    free(pairs);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parser
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            arr[size++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int* result = solution(arr, size, line);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", result[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

One pass to create pairs O(n) + sorting O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Stores array of (value, function_result) pairs

⚡ Linearithmic Space

34.6K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Transform Then Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler