Problem Overview

You are given an array of people represented as pairs of integers, where each pair is in the form (h, k):

• h represents the height of a person.
• k represents the number of people in front of this person who have a height greater than or equal to h.

Your task is to reconstruct the original queue that satisfies all the given conditions.

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

---

Intuition / Approach

This problem seems tricky at first because both height and k are interdependent.
However, with a clever sorting and insertion strategy, we can reconstruct the queue step by step.

Key Insight:

1. Sort the people first so that taller people are placed before shorter ones.
   • For people with the same height, sort them by their k value in ascending order.
   • This ensures that when we insert people into the queue, shorter people do not affect the order of taller ones.
2. Insert each person into the queue based on their k value.
   • The k value represents the position at which this person should appear in the queue because exactly k taller (or equal height) people must be in front of them.

This approach ensures that every time we insert someone, the condition for their k value automatically holds true, since all previously inserted people are taller or equal in height.

---

Algorithm Explanation

1. Sort the input array:
   • Sort primarily by height in descending order (h from high to low).
   • If two people have the same height, sort by k in ascending order.
2. Insert people one by one:
   • Initialize an empty List to represent the queue.
   • For each person in the sorted list:
     • Insert them at the position specified by their k value.
     • Since the list automatically shifts elements to the right, the relative ordering is preserved.
3. Convert the list back to an array and return it.

---

Java Code Implementation

import java.util.*;

public class QueueReconstructionByHeight {

    public int[][] reconstructQueue(int[][] people) {
        // Step 1: Sort the array
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];  // sort by k ascending if height is same
            } else {
                return b[0] - a[0];  // sort by height descending
            }
        });

        // Step 2: Use a list to insert people based on k value
        List<int[]> result = new ArrayList<>();
        for (int[] person : people) {
            result.add(person[1], person);  // insert at index = k
        }

        // Step 3: Convert list back to 2D array
        return result.toArray(new int[people.length][2]);
    }

    // Example usage
    public static void main(String[] args) {
        QueueReconstructionByHeight solution = new QueueReconstructionByHeight();
        int[][] people = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
        int[][] result = solution.reconstructQueue(people);

        System.out.println("Reconstructed Queue:");
        for (int[] person : result) {
            System.out.println(Arrays.toString(person));
        }
    }
}

---

Dry Run Example

Let’s take the input:
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

1. After Sorting: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
2. Insert one by one:
   • Insert [7,0] → [[7,0]]
   • Insert [7,1] → [[7,0], [7,1]]
   • Insert [6,1] → [[7,0], [6,1], [7,1]]
   • Insert [5,0] → [[5,0], [7,0], [6,1], [7,1]]
   • Insert [5,2] → [[5,0], [7,0], [5,2], [6,1], [7,1]]
   • Insert [4,4] → [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Final Output:
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

---

Complexity Analysis

Time Complexity:

• Sorting takes O(n log n).
• Insertion into the list for each person takes O(n) in the worst case.
• Therefore, total time complexity = O(n²).

Space Complexity:

• We use an additional list to build the result.
• Space complexity = O(n).

---

Alternative Approaches

1. Using LinkedList for insertion:
   • A LinkedList could be used for insertion to avoid shifting elements.
   • However, since add(index, element) still requires traversal to the index position, time complexity remains O(n²).
2. Using a Segment Tree (Advanced):
   • In theory, one could use a segment tree or binary indexed tree to improve the insertion logic, but that adds unnecessary complexity.
   • For this problem size, the sorting + list insertion approach is optimal and clear.