Sort the People - Practice Coding Problems

Sort the People - Problem

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the i-th person.

Return names sorted in descending order by the people's heights.

Input & Output

Example 1 — Basic Sorting

$ Input: names = ["Mary","John","Emma"], heights = [180,165,170]

› Output: ["Mary","Emma","John"]

💡 Note: Mary is tallest (180), Emma is second (170), John is shortest (165). Sorted in descending order by height.

Example 2 — Different Names

$ Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]

› Output: ["Bob","Alice","Bob"]

💡 Note: Bob (185) is tallest, Alice (155) is middle, Bob (150) is shortest. Names can repeat but heights are distinct.

Example 3 — Two People

$ Input: names = ["IEO","Sgizfdfrims"], heights = [165,170]

› Output: ["Sgizfdfrims","IEO"]

💡 Note: Sgizfdfrims (170) is taller than IEO (165), so comes first in descending order.

Constraints

n == names.length == heights.length
1 ≤ n ≤ 10³
1 ≤ names[i].length ≤ 20
1 ≤ heights[i] ≤ 10⁵
heights[i] are distinct
names[i] consists of lower and upper case English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Names array and heights array with corresponding indices

Process

Sort by heights in descending order while maintaining name-height association

Output

Names array sorted by descending height order

Key Takeaway

🎯 Key Insight: Pair data elements together before sorting to maintain relationships between corresponding array elements

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to pair names with their corresponding heights, sort by height in descending order, then extract the names. The optimal approach uses built-in sort with custom comparator. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Pair Sorting	O(n log n)	O(n)	Create name-height pairs and sort directly with custom comparator
Brute Force Bubble Sort	O(n²)	O(n)	Manually sort by repeatedly swapping adjacent elements
Sort with Index Mapping	O(n log n)	O(n)	Create index array, sort by heights, then map to names

Direct Pair Sorting — Algorithm Steps

Step 1: Create (name, height) pairs
Step 2: Sort pairs by height using custom comparator (descending)
Step 3: Extract names from sorted pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Pairs

Combine each name with its height

Sort Pairs

Sort by height using custom comparator

Extract Names

Get names from sorted pairs

Code -

solution.c — C

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

typedef struct {
    char name[50];
    int height;
} Person;

int compare(const void* a, const void* b) {
    Person* pa = (Person*)a;
    Person* pb = (Person*)b;
    return pb->height - pa->height; // Descending order
}

char** solution(char** names, int* heights, int n) {
    // Create pairs of (name, height)
    Person* people = (Person*)malloc(n * sizeof(Person));
    for (int i = 0; i < n; i++) {
        strcpy(people[i].name, names[i]);
        people[i].height = heights[i];
    }
    
    // Sort pairs by height in descending order
    qsort(people, n, sizeof(Person), compare);
    
    // Extract names from sorted pairs
    char** result = (char**)malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        result[i] = (char*)malloc(50 * sizeof(char));
        strcpy(result[i], people[i].name);
    }
    
    free(people);
    return result;
}

int main() {
    // Simplified parsing for demonstration
    char** names = (char**)malloc(3 * sizeof(char*));
    int* heights = (int*)malloc(3 * sizeof(int));
    
    names[0] = "Mary"; names[1] = "John"; names[2] = "Emma";
    heights[0] = 180; heights[1] = 165; heights[2] = 170;
    
    char** result = solution(names, heights, 3);
    
    printf("[");
    for (int i = 0; i < 3; i++) {
        printf("\"%s\"", result[i]);
        if (i < 2) printf(",");
    }
    printf("]\n");
    
    for (int i = 0; i < 3; i++) free(result[i]);
    free(result);
    free(names);
    free(heights);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Built-in sort algorithm is typically O(n log n) merge sort or quicksort

⚡ Linearithmic

Space Complexity

O(n)

Extra space for storing name-height pairs

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~5 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

Direct Pair Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler