> ## Documentation Index > Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt > Use this file to discover all available pages before exploring further. > ## Agent Instructions > leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform. > Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package. > Examples are backed by tests; copy them verbatim. # Queue Reconstruction by Height Python Solution > Tested Python solution for LeetCode 406 with 19 pytest cases. Generate a practice environment with lcpy. LeetCode 406, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/queue-reconstruction-by-height/description/). Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook: ```bash theme={"theme":{"light":"github-light","dark":"github-dark"}} lcpy gen -n 406 # by problem number lcpy gen -s queue_reconstruction_by_height # by problem name ``` ## Problem 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_i, 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). ### Examples ``` 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. ``` 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 <= h_i <= 10^6` * `0 <= k_i < people.length` * It is guaranteed that the queue can be reconstructed. ## Solution Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/queue_reconstruction_by_height/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/queue_reconstruction_by_height/test_solution.py): ```python theme={"theme":{"light":"github-light","dark":"github-dark"}} class Solution: # Time: O(n^2) (n <= 2000, insertion into a list is linear) # Space: O(n) def reconstruct_queue(self, people: list[list[int]]) -> list[list[int]]: # Tall first (so later, shorter insertions cannot invalidate earlier # placements), then fewest taller-in-front first; insert at index k. ordered = sorted(people, key=lambda p: (-p[0], p[1])) queue: list[list[int]] = [] for height, k in ordered: queue.insert(k, [height, k]) return queue ``` ## Complexity | Time | Space | | - | - | | O(n^2) (n \<= 2000, insertion into a list is linear) | O(n) | ## Tags This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.