algoadvance

Leetcode 406. Queue Reconstruction by Height

Problem Statement

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[j] is people[i] in the input).

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]]

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 <= h_i <= 10^6
• 0 <= k_i < people.length
• It is guaranteed that the queue can be reconstructed.

Clarifying Questions

1. Can there be identical [h, k] pairs in the input?
   • No, each [h_i, k_i] pair is unique as per the problem constraints.
2. What should be returned if the input list is empty?
   • The input list will always contain at least one element based on the constraints.

Strategy

1. Sorting:
   • First, we need to sort people by height in descending order. For people with the same height, we sort them by their k value in ascending order.
   • This helps because when inserting into the queue, if two people have the same height, the one with a smaller k value should be positioned first.
2. Insertion:
   • Iterate over the sorted people list and insert each person at the index equal to their k value in the result queue.
   • The insert operation respects the k value since inserting at an index shifts elements to the right.

Detailed Steps

• Sort people using a custom comparator:
  • First by height in descending order.
  • Second by k in ascending order.
• Initialize an empty result list.
• Insert each person into the result list at the index equal to their k value.

Example Walkthrough

Input: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

• Sorted: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
• Step-by-step insertions:
  • Insert [7,0] at index 0 -> [[7,0]]
  • Insert [7,1] at index 1 -> [[7,0],[7,1]]
  • Insert [6,1] at index 1 -> [[7,0],[6,1],[7,1]]
  • Insert [5,0] at index 0 -> [[5,0],[7,0],[6,1],[7,1]]
  • Insert [5,2] at index 2 -> [[5,0],[7,0],[5,2],[6,1],[7,1]]
  • Insert [4,4] at index 4 -> [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> reconstructQueue(std::vector<std::vector<int>>& people) {
        // Sorting the people array
        std::sort(people.begin(), people.end(),
                  [](const std::vector<int>& a, const std::vector<int>& b) {
                      return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
                  });

        std::vector<std::vector<int>> result;
        // Inserting each person into the result based on their k value
        for (const auto& person : people) {
            result.insert(result.begin() + person[1], person);
        }

        return result;
    }
};

Time Complexity

• Sorting: (O(N \log N)), where (N) is the length of the people array.
• Insertion: (O(N^2)) in the worst case due to the need for shifting elements.

Overall, the time complexity is (O(N^2)), which is efficient enough for the given constraint (1 <= people.length <= 2000).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?