406. Queue Reconstruction by Height LeetCode Solution

In this guide, you will get 406. Queue Reconstruction by Height LeetCode Solution with the best time and space complexity. The solution to Queue Reconstruction by Height problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Queue Reconstruction by Height solution in C++
  4. Queue Reconstruction by Height solution in Java
  5. Queue Reconstruction by Height solution in Python
  6. Additional Resources
406. Queue Reconstruction by Height LeetCode Solution image

Problem Statement of 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.

See also  845. Longest Mountain in Array LeetCode Solution

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.

Complexity Analysis

  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

406. Queue Reconstruction by Height LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    vector<vector<int>> ans;

    ranges::sort(people, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });

    for (const vector<int>& p : people)
      ans.insert(ans.begin() + p[1], p);

    return ans;
  }
};
/* code provided by PROGIEZ */

406. Queue Reconstruction by Height LeetCode Solution in Java

class Solution {
  public int[][] reconstructQueue(int[][] people) {
    List<int[]> ans = new ArrayList<>();

    Arrays.sort(people,
                (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]));

    for (final int[] p : people)
      ans.add(p[1], p);

    return ans.stream().toArray(int[][] ::new);
  }
}
// code provided by PROGIEZ

406. Queue Reconstruction by Height LeetCode Solution in Python

class Solution:
  def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
    ans = []

    people.sort(key=lambda x: (-x[0], x[1]))

    for p in people:
      ans.insert(p[1], p)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: