LeetCode 406: Queue Reconstruction by Height Solution

Master LeetCode problem 406 (Queue Reconstruction by Height), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

406. Queue Reconstruction by Height

Medium

Array Binary Indexed Tree Segment Tree Sorting

Problem Explanation

Explanation

To solve this problem, we can first sort the people array in decreasing order of height and increasing order of number of people in front. Then, we can iterate through the sorted array and insert each person into their correct position in the final reconstructed queue.

Algorithm:

Sort the people array in descending order of height and ascending order of number of people in front.
Iterate through the sorted array and insert each person at the index equal to their number of people in front.
As we insert people one by one, the taller people have already been added at their correct positions, so the shorter people do not affect the taller people's positions.

Time Complexity:

The time complexity of this algorithm is O(n^2) where n is the number of people.

Space Complexity:

The space complexity of this algorithm is O(n) to store the reconstructed queue.

Solution Code

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> queue = new ArrayList<>();
        
        for (int[] person : people) {
            queue.add(person[1], person);
        }
        
        return queue.toArray(new int[people.length][2]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 406 (Queue Reconstruction by Height)?

This page provides optimized solutions for LeetCode problem 406 (Queue Reconstruction by Height) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 406 (Queue Reconstruction by Height)?

The time complexity for LeetCode 406 (Queue Reconstruction by Height) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 406 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 406 in Java, C++, or Python.

Back to LeetCode Solutions