Algorithm

Problem Name: 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] = [hi, ki]` represents the `ith` person of height `hi` with exactly `ki` other people in front who have a height greater than or equal to `hi`.

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] = [hj, kj]` is the attributes of the `jth` 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 <= 106`
• `0 <= ki < people.length`
• It is guaranteed that the queue can be reconstructed.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int cmp(const void *a, const void *b) {
int c;
c = (*(int **)b)[0] - (*(int **)a)[0];  // height decreasing order
if (c) return c;
c = (*(int **)a)[1] - (*(int **)b)[1];  // number increasing order
return c;
}
int reconstruct(int **q, int **p, int sz) {
int i, j, k;
int t[2];

qsort(p, sz, sizeof(int *), cmp);

for (i = 0; i  <  sz; i ++) {
q[i][0] = p[i][0];
q[i][1] = p[i][1];
if (q[i][1] > i) {
return 0;  // no way to make it!
}
if (q[i][1]  <  i) {  // move it ahead
t[0] = q[i][0];
t[1] = q[i][1];
for (j = i; j > t[1]; j --) {  // find a slot ahead by pulling some one slot back
q[j][0] = q[j - 1][0];
q[j][1] = q[j - 1][1];
}
q[j][0] = t[0];  // done with current one
q[j][1] = t[1];
}
}
return 1;
}
int** reconstructQueue(int** people, int peopleRowSize, int peopleColSize, int* returnSize) {
int **q, *buff;
int i;

*returnSize = 0;
if (peopleRowSize == 0 || !people) {
return NULL;
}
q = malloc(peopleRowSize * sizeof(int *));
buff = malloc(peopleRowSize * peopleColSize * sizeof(int));
//assert(q && buff);

for (i = 0; i  <  peopleRowSize; i ++) {
q[i] = &buff[i * peopleColSize];
}

if (!reconstruct(q, people, peopleRowSize)) {
free(q[0]);
free(q);
q = NULL;
*returnSize = 0;
} else {
*returnSize = peopleRowSize;
}

return q;
}
``````
Copy The Code &

Input

cmd
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Output

cmd
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

#2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
List < int[]> result = new ArrayList<>();
for (int[] p : people) {
}
int n = people.length;
return result.toArray(new int[n][2]);
}
}
``````
Copy The Code &

Input

cmd
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Output

cmd
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const reconstructQueue = function (people) {
const h = 0
const k = 1
people.sort((a, b) => (a[h] == b[h] ? a[k] - b[k] : b[h] - a[h]))
let queue = []
for (let person of people) {
queue.splice(person[k], 0, person)
}
return queue
}
``````
Copy The Code &

Input

cmd
people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Output

cmd
[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def reconstructQueue(self, people):
arr = [0] * len(people)
people.sort()
for h, k in people:
cnt = 0
for i in range(len(arr)):
if not arr[i] or arr[i][0] == h:
cnt += 1
if cnt == k + 1:
arr[i] = [h, k]
return arr
``````
Copy The Code &

Input

cmd
people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Output

cmd
[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

#5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0406_QueueReconstructionByHeight
{
public int[][] ReconstructQueue(int[][] people)
{
Array.Sort(people, new PeopleComparer());

var result = new List < int[]>(people.Length);
foreach (var p in people)
result.Insert(p[1], p);
return result.ToArray();
}

private class PeopleComparer : IComparer < int[]>
{
public int Compare(int[] x, int[] y)
{
return x[0] == y[0] ? x[1].CompareTo(y[1]) : -x[0].CompareTo(y[0]);
}
}
}
}
``````
Copy The Code &

Input

cmd
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Output

cmd
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]