We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Queue Reconstruction by Height

Number: 406

Difficulty: Medium

Paid? No

Companies: PhonePe, Google, Meta

Problem Description

Given an array of people where each person is represented as [h, k] (h is the person's height and k is the number of people in front of this person who have a height greater than or equal to h), reconstruct the queue.

Key Insights

  • Sort the array in descending order by height; for people with equal height, sort in ascending order by k.
  • When inserting a person into the result list, their k value indicates the index at which they should be placed.
  • This greedy approach guarantees that each person is inserted after all taller or equal height persons have already been placed.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case due to the insertion process in the list. Space Complexity: O(n) for storing the output queue.

Solution

The solution leverages a greedy algorithm. First, sort the input array such that taller people come first and, for the same height, the person with a smaller k comes first. By doing this, when you iterate over the sorted list and insert each person at the index equal to their k value, the relative order of people already inserted (who are taller or of the same height) remains valid, fulfilling the condition of exactly k people in front who are taller or equal.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def reconstructQueue(self, people):
        # Sort people: first by descending height; if heights are equal, sort by ascending k value.
        people.sort(key=lambda person: (-person[0], person[1]))
        
        # Initialize result list
        queue = []
        
        # Insert each person in the list at the index equal to their k-value.
        for person in people:
            queue.insert(person[1], person)  # person[1] is the k value indicating the index
        return queue

# Example usage:
# solution = Solution()
# print(solution.reconstructQueue([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]))
← Back to All Questions