keetcoder

# 406. Queue Reconstruction by Height

LeetCode Problem Link (opens new window)

Suppose there is a group of people standing in a queue in random order. Each person's characteristics are represented by an array people (not necessarily in order). Each people[i] = [hi, ki] represents the i-th person's height as hi, and there are exactly ki people in front of this person who have a height greater than or equal to hi.

Please reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as the array queue, where queue[j] = [hj, kj] is the attributes of the person standing in the j-th position of the queue (the person at queue[0] is 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 and no taller or equal height people in front.
    • Person 1 has height 7 and no taller or equal height people in front.
    • Person 2 has height 5 with 2 taller or equal height people in front, which are persons 0 and 1.
    • Person 3 has height 6 with 1 taller or equal height person in front, which is person 1.
    • Person 4 has height 4 with 4 taller or equal height people in front, which are persons 0, 1, 2, and 3.
    • Person 5 has height 7 with 1 taller or equal height person in front, which is person 1.
    • Therefore, [[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 <= ki < people.length

The problem data ensures that the queue can be reconstructed.

# Approach

This problem involves two dimensions, h and k. When faced with problems involving two dimensions, one must decide how to fixate one dimension before rearranging based on the other.

If anyone has done 0135.Candy (opens new window), they might find some similarities with this problem.

As emphasized in 0135.Candy (opens new window), when dealing with two dimensions, always try to fix one dimension first before greeding on the other dimension. Considering both dimensions together will undoubtedly result in missing both.

The main confusion may lie in whether to order first by k or first by h, i.e., should we sort by h or k?

Sorting by increasing k will result in neither k order nor height order being satisfied, meaning neither dimension will be resolved.

What if we sort by height h? We should sort the heights in descending order (and for same heights, sort by k in ascending order) to have taller people in front.

By sorting this way, one dimension can be determined: height, where all preceding nodes will be taller than the present node!

Thus, simply reinserting into the queue using k as the index suffices. Why?

Take the example {5,2} from the diagram:

406. Queue Reconstruction by Height

After sorting by height, priority is given to inserting the people with higher height. Subsequent insertions won't affect already inserted nodes as they have been placed in accordance with k values. Eventually, the queue reflects the desired properties.

Upon sorting heights in descending order: Local Optimality: Prioritize inserting people according to their k values after sorting by height, ensuring each insertion satisfies the queue's conditions.

Global Optimality: Upon completing all insertions, the entire queue satisfies the properties outlined in the problem statement.

Local optimizations lead to global optimization; if no counterexamples exist, then a greedy approach should be considered.

Some might question how one can be certain that local optimization leads to global optimization. Is there mathematical proof?

As discussed in the introduction to Greedy Algorithm Fundamentals (opens new window), if manual simulation suggests that local optimization can lead to global optimization and no counterexamples can be thought of, then give the greedy approach a try. A formal mathematical proof is not our concern here.

Returning to this problem, the entire insertion process is as follows:

Sorted people: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Insertion process:

  • Insert [7,0]: [[7,0]]
  • Insert [7,1]: [[7,0],[7,1]]
  • Insert [6,1]: [[7,0],[6,1],[7,1]]
  • Insert [5,0]: [[5,0],[7,0],[6,1],[7,1]]
  • Insert [5,2]: [[5,0],[7,0],[5,2],[6,1],[7,1]]
  • Insert [4,4]: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

The queue is thus reconstructed according to the problem requirements.

C++ code as follows:

// Version 1
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  • Time Complexity: O(nlog n + n^2)
  • Space Complexity: O(n)

However, using vector can be very time-consuming. In C++, if inserting elements exceeds the pre-allocated normal array size, the vector undergoes a resizing operation, essentially allocating double the current array size and copying the data to a larger array.

Therefore, using a vector (dynamic array) for insertion is time-consuming. When resizing and copying, each insertion operation can be O(n^2), and possibly more than O(n^2) if multiple copies occur.

Switching to a list, the C++ code is as follows:

// Version 2
class Solution {
public:
    // Sort height in descending order (for same height, place smaller k first)
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        list<vector<int>> que; // List uses a linked list, making insertions much more efficient than with vector
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // Insert at position index
            std::list<vector<int>>::iterator it = que.begin();
            while (position--) { // Finding the insertion position
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • Time Complexity: O(nlog n + n^2)
  • Space Complexity: O(n)

You can submit both versions of the code to see the difference!

The performance difference between using arrays and lists for this problem is explained in detail in Queue Reconstruction by Height (Vector Principle Explanation) (opens new window)

# Conclusion

In cases where two dimensions need to be considered simultaneously, we've solved two problems. The other one is 0135.Candy (opens new window).

The technique is to fix one dimension and then greedily handle the other. Considering both together will miss both.

This problem can be said to be significantly more challenging than 0135.Candy (opens new window), and the strategy of greed is rather clever.

Finally, I provided two versions of the code. It is apparent that using list (implemented using linked lists) in C++ is much more efficient than vector (array).

Using a specific language's container capabilities and features will, to varying degrees, affect efficiency.

Many claim that the language used for algorithm exercises doesn’t matter much, focusing mainly on algorithmic thinking, and I agree but also disagree.

For those reading others’ solutions, the language used in the solution indeed doesn’t matter much as long as the explanation covers the optimization points related to language features. Everyone should be able to understand and modify accordingly when using their language.

For those writing solutions, the language used indeed matters a lot. If you haven't proficiently learned the language and claim that algorithms and programming languages are irrelevant, this could misguide others.

That's why I consistently use C++ for writing solutions.

# Other Language Versions

# Java

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // Sort heights in descending order (if height is the same, sort by k in ascending order)
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> que = new LinkedList<>();

        for (int[] p : people) {
            que.add(p[1],p); // LinkedList.add(index, value) inserts value at the specified index
        }

        return que.toArray(new int[people.length][]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1])) # Sort by height desc, by k asc when height is the same
        que = []

        # Greedily insert each person based on the second dimension k
        for p in people:
            que.insert(p[1], p)
        return que
1
2
3
4
5
6
7
8
9

# Go

func reconstructQueue(people [][]int) [][]int {
    // Sort by descending heights, establish the relative positions for tallest
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1] // Sort by k in ascending order when heights are equal
        }
        return people[i][0] > people[j][0] // Sort by height in descending order
    })

    // Insert according to k in the sorted order, prioritizing smaller k
	for i, p := range people {
		copy(people[p[1]+1 : i+1], people[p[1] : i+1])  // Shift right to create space
		people[p[1]] = p
	}
	return people
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// List implementation
func reconstructQueue(people [][]int) [][]int {
     sort.Slice(people,func (i,j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1] // Sort by k when heights are equal
        }
        return people[i][0] > people[j][0]
    })
    l := list.New()      // Create list
    for i:=0; i < len(people); i++ {
        position := people[i][1]
        mark := l.PushBack(people[i])      // Insert element
        e := l.Front()
        for position != 0 {      // Get relative position
            position--
            e = e.Next()
        }
        l.MoveBefore(mark, e)    // Move to position
    }
    res := [][]int{}
    for e := l.Front(); e != nil; e = e.Next() {
        res = append(res, e.Value.([]int))
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# JavaScript

var reconstructQueue = function(people) {
    let queue = []
    people.sort((a, b ) => {
        if(b[0] !== a[0]) {
            return b[0] - a[0]
        } else {
            return a[1] - b[1]
        }
        
    })

    for(let i = 0; i < people.length; i++) {
        queue.splice(people[i][1], 0, people[i])
    }
    return queue
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Rust

impl Solution {
    pub fn reconstructQueue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut queue = vec![];
        people.sort_by(|a, b| {
            if a[0] == b[0] {
                return a[1].cmp(&b[1]);
            }
            b[0].cmp(&a[0])
        });
        queue.push(people[0].clone());
        for v in people.iter().skip(1) {
            queue.insert(v[1] as usize, v.clone());
        }
        queue
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# C

int cmp(const void *p1, const void *p2) {
    int *pp1 = *(int**)p1;
    int *pp2 = *(int**)p2;
    // Sort by k ascending when heights are equal
    // Sort by height descending otherwise
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
}

// Shift elements between start and end one position backward
void moveBack(int **people, int peopleSize, int start, int end) {
    int i;
    for(i = end; i > start; i--) {
        people[i] = people[i-1];
    }
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    int i;
    // Sort by height descending and then by k ascending
    qsort(people, peopleSize, sizeof(int*), cmp);

    for(i = 0; i < peopleSize; ++i) {
        int position = people[i][1];
        int *temp = people[i];
        moveBack(people, peopleSize, position, i);
        people[position] = temp;
    }
    
    *returnSize = peopleSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
    for(i = 0; i < peopleSize; ++i) {
        (*returnColumnSizes)[i] = 2;
    }
    return people;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# TypeScript

function reconstructQueue(people: number[][]): number[][] {
    people.sort((a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return b[0] - a[0];
    });
    const resArr: number[][] = [];
    for (let i = 0, length = people.length; i < length; i++) {
        resArr.splice(people[i][1], 0, people[i]);
    }
    return resArr;
};
1
2
3
4
5
6
7
8
9
10
11

# Scala

object Solution {
  import scala.collection.mutable
  def reconstructQueue(people: Array[Array[Int]]): Array[Array[Int]] = {
    val person = people.sortWith((a, b) => {
      if (a(0) == b(0)) a(1) < b(1)
      else a(0) > b(0)
    })

    var que = mutable.ArrayBuffer[Array[Int]]()

    for (per <- person) {
      que.insert(per(1), per)
    }

    que.toArray
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# C#

public class Solution
{
    public int[][] ReconstructQueue(int[][] people)
    {
        Array.Sort(people, (a, b) =>
        {
            if (a[0] == b[0])
            {
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });
        var res = new List<int[]>();
        for (int i = 0; i < people.Length; i++)
        {
            res.Insert(people[i][1], people[i]);
        }
        return res.ToArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Last updated:: 9/4/2025, 3:19:38 PM

← 13. Queue Reconstruction by Height (Vector Explanation) →

Copyright © 2025 keetcoder