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 <= 20000 <= hi <= 1060 <= 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;
}
Input
Output
#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) {
result.add(p[1], p);
}
int n = people.length;
return result.toArray(new int[n][2]);
}
}
Input
Output
#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
}
Input
Output
#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
Input
Output
#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]);
}
}
}
}
Input
Output