406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each $people[i]=[h_{,}{k}_i]$ represents the $i^{th}$ person of height $h_i$ with exactly $k_i$ other people in front who have a height greater than or equal to $h_i$.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where $queue[j]=[h_j,k_j]$ is the attributes of the $j^{th}$ person in the queue (queue[0] is the person at the front of the queue).
 

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

• 1 <= people.length <= 2000
• $0<=hi<=10^6$
• $0<=k_i<people.length$
• It is guaranteed that the queue can be reconstructed.

From: LeetCode
Link: 406. Queue Reconstruction by Height

Solution:

Ideas:

1. Sorting: As before, we sort the people based on height and the number of people in front.

2. Constructing the Queue: We insert each person into the queue at the index specified by their k value. We make sure to shift the queue as needed to maintain the order.

Code:

// Comparator function for sorting the people array
int cmp(const void *a, const void *b) {
    int *personA = *(int **)a;
    int *personB = *(int **)b;
    if (personA[0] == personB[0]) {
        return personA[1] - personB[1]; // sort by k in ascending order
    }
    return personB[0] - personA[0]; // sort by height in descending order
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
    // Step 1: Sort the people
    qsort(people, peopleSize, sizeof(int *), cmp);
    
    // Step 2: Initialize the queue with a maximum size
    int **queue = (int **)malloc(sizeof(int *) * peopleSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * peopleSize);
    *returnSize = 0;

    // Step 3: Insert into the queue
    for (int i = 0; i < peopleSize; i++) {
        // Allocate memory for the current person
        int *person = (int *)malloc(sizeof(int) * 2);
        person[0] = people[i][0]; // height
        person[1] = people[i][1]; // k
        
        // Insert the person at the index specified by k
        for (int j = 0; j < *returnSize; j++) {
            // If j is equal to k, insert the person here
            if (j == person[1]) {
                // Shift all elements to the right
                for (int l = *returnSize; l > j; l--) {
                    queue[l] = queue[l - 1];
                }
                queue[j] = person; // Place the person
                (*returnSize)++; // Increase the size of the queue
                break; // Exit the loop after insertion
            }
        }

        // If not inserted, it means it should go to the end
        if (person[1] == *returnSize) {
            queue[*returnSize] = person;
            (*returnSize)++;
        }
    }

    // Set the sizes of the arrays in returnColumnSizes
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 2; // Each person has two attributes
    }

    return queue;
}