Sort the People

Leetcode Problem:

• Sort the People

Summary

• Given an array of names and heights, sort the names in descending order by height.

Approach

• Merge Sort algorithm is used to sort the heights array first, then use the sorted heights array to sort the names array.

Complexity

• O(n log n)

Explain

• The merge_sort function is a recursive function that divides the array into two halves until each subarray has one element
• The merge function then merges the subarrays back together in sorted order
• After sorting the heights array, the names array is sorted based on the heights array
• The names array is then returned in a vector of strings.

Solution Code:

class Solution {
public:
    vector h;
    int tmp[1001];
    void merge(int* arr, int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = l;
        while(i <= mid && j <= r){
            int num1 = arr[i];
            int num2 = arr[j];
            if(h[num1] >= h[num2]){
                tmp[cur++] = arr[i++];
            }else{
                tmp[cur++] = arr[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = arr[i++];
        }
        for(i = l; i < cur; i++){
            arr[i] = tmp[i];
        }
    }
    void merge_sort(int* arr, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(arr, l, mid);
        merge_sort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    vector sortPeople(vector& names, vector& heights) {
        h = heights;
        int* arr = new int[heights.size()];
        for(int i = 0 ; i < heights.size(); i++){
            arr[i] = i;
        }
        merge_sort(arr, 0, heights.size()-1);
        vector ans;
        for(int i = 0 ; i < heights.size(); i++){
            int n = arr[i];
            ans.push_back(names[n]);
        }
        return ans;
    }
};