medium Queue Reconstruction by Height

Problem Statement

You are given an array of people people, containing some attributes of people standing in the queue (In random order). Here, people[i] is a pair [h_i, k_i], where h_i represents the height of the i^th person, and k_i represents the exact number of people in front of the i^th person who have a height greater than or equal to h_i in the given queue.

Reconstruct and return the queue so that the given conditions are met.

Examples

1. Example 1:

   • Input: people = [[6, 0], [5, 1], [5, 0], [7, 0], [7, 1], [6, 2]]
   • Expected Output: [[5,0],[5,1],[6,0],[7,0],[6,2],[7,1]]
   • Justification:
     • Person 0 has height 6 with no other people taller or the same height in front.
     • Person 1 has a height 5 with one other person taller or the same height in front, which is 0.
     • Person 2 has height 6 with no other people taller or the same height in front.
     • Person 3 has height 7 with no other people taller or the same height in front.
     • Person 4 has height 6 with two other people taller or the same height in front, which are 2 and 3.
     • Person 5 has height 7 with one other person taller or the same height in front, which is 3.

2. Example 2:

   • Input: people = [[4, 0], [5, 1], [7, 0], [6, 1]]
   • Expected Output: [[4,0],[7,0],[5,1],[6,1]]
   • Justification:
     • Person 0 has height 4 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 a height 5 with one other person taller or the same height in front, which is 1.
     • Person 3 has height 6 with one other person taller or the same height in front, which is 1.

3. Example 3:

   • Input: people = [[7, 0], [6, 1], [5, 2], [6, 0], [4, 4], [5, 1]]
   • Expected Output: [[6,0],[5,1],[5,2],[6,1],[4,4],[7,0]]
   • Justification:
     • Person 0 has height 6 with no other people taller or the same height in front.
     • Person 1 has a height 5 with one other person taller or the same height in front, which is 0.
     • Person 2 has height 5 with two other people taller or the same height in front, which are 0 and 1.
     • Person 3 has height 6 with one other person taller or the same height in front, which is 0.
     • Person 4 has height 4 with four other people taller or the same height in front, which are 0, 1, 2, and 3.
     • Person 5 has height 7 with no other person taller or the same height in front.

Constraints:

• 1 <= people.length <= 2000
• 0 <= h_i <= 106
• 0 <= k_i < people.length
• It is guaranteed that the queue can be reconstructed.

Solution

To solve this problem, we need to reconstruct the queue based on given heights and the number of taller or equal height people in front. We will use a segment tree to efficiently place each person in the correct position in the queue.

The algorithm works by first sorting the people based on their heights in ascending order. For people with the same height, we sort them by the number of people in front in descending order. We then build a segment tree to keep track of vacant spots in the queue. As we iterate through the sorted list, we use the segment tree to find the correct position for each person and update the tree accordingly.

Step-by-Step Algorithm

1. Sort the Input Array:

   • Sort the people array in ascending order based on height (hi).
   • If two people have the same height, sort them by the number of people in front (ki) in descending order.
   • This sorting ensures that shorter people are placed first, and ties are handled by placing the person with more people in front first.

2. Initialize Data Structures:

   • Create an array segmentTree of size 4 * n to represent the segment tree, where n is the number of people.
   • Create a list resultQueue with n null elements to store the final reconstructed queue.

3. Build the Segment Tree:

   • Define a recursive method buildSegmentTree to build the segment tree.
   • Step-by-Step Process:
     • If the current segment is a leaf node (i.e., left == right), set the segment tree value to 1, representing one vacant spot.
     • Calculate the mid-point of the current segment as mid = left + (right - left) / 2.
     • Recursively build the left and right subtrees.
     • Set the current segment tree value to the sum of its left and right children, representing the total number of vacant spots in the current segment.

4. Place People in the Queue:

   • Iterate through the sorted list of people.
   • For each person, use the segment tree to find the correct position in the queue and place them.
   • Define a recursive method query to update the segment tree and find the correct position for each person.
   • Step-by-Step Process:
     • If the current segment is a leaf node (i.e., left == right), place the person at this position in the resultQueue, and decrement the segment tree value.
     • If the current segment cannot accommodate the required position, return.
     • Calculate the mid-point of the current segment as mid = left + (right - left) / 2.
     • If the left subtree can accommodate the required position, recursively query the left subtree.
     • Otherwise, recursively query the right subtree with the updated position (position - segmentTree[2 * index + 1]). At this point, we are adjusting the segmentTree[2 * index + 1] points, which are already covered in the left subtree.
     • Decrement the segment tree value to reflect the reduced number of vacant spots.

5. Convert Result List to Array:

   • Convert the resultQueue list to a 2D array and return it.

Algorithm Walkthrough

Let's walk through the algorithm with the input [[6, 0], [5, 1], [5, 0], [7, 0], [7, 1], [6, 2]].

Step 1: Sort the Input Array

The input array is sorted as follows:

Sorted array: [[5, 1], [5, 0], [6, 2], [6, 0], [7, 1], [7, 0]]

Step 2: Initialize Data Structures

• segmentTree = new int[4 * 6] initialized with zeroes.
• resultQueue = new ArrayList<>(Collections.nCopies(6, null))

Step 3: Build the Segment Tree

Initial Call:

• buildSegmentTree(segmentTree, 0, 0, 5)

Recursive Calls:

• Divide the segment [0, 5]:

  • mid = (0 + 5) / 2 = 2

• Left Subtree:

  • buildSegmentTree(segmentTree, 1, 0, 2)

  • Divide the segment [0, 2]:

    • mid = (0 + 2) / 2 = 1

  • Left Subtree:

    • buildSegmentTree(segmentTree, 3, 0, 1)

    • Divide the segment [0, 1]:

      • mid = (0 + 1) / 2 = 0

    • Left Subtree (Leaf Node):

      • buildSegmentTree(segmentTree, 7, 0, 0)

      • Since left == right, set segmentTree[7] = 1.

    • Right Subtree (Leaf Node):

      • buildSegmentTree(segmentTree, 8, 1, 1)

      • Since left == right, set segmentTree[8] = 1.

    • Set segmentTree[3] = segmentTree[7] + segmentTree[8] = 2.

  • Right Subtree (Leaf Node):

    • buildSegmentTree(segmentTree, 4, 2, 2)

    • Since left == right, set segmentTree[4] = 1.

  • Set segmentTree[1] = segmentTree[3] + segmentTree[4] = 3.

• Right Subtree:

  • buildSegmentTree(segmentTree, 2, 3, 5)

  • Divide the segment [3, 5]:

    • mid = (3 + 5) / 2 = 4

  • Left Subtree:

    • buildSegmentTree(segmentTree, 5, 3, 4)

    • Divide the segment [3, 4]:

      • mid = (3 + 4) / 2 = 3

    • Left Subtree (Leaf Node):

      • buildSegmentTree(segmentTree, 11, 3, 3)

      • Since left == right, set segmentTree[11] = 1.

    • Right Subtree (Leaf Node):

      • buildSegmentTree(segmentTree, 12, 4, 4)

      • Since left == right, set segmentTree[12] = 1.

    • Set segmentTree[5] = segmentTree[11] + segmentTree[12] = 2.

  • Right Subtree (Leaf Node):

    • buildSegmentTree(segmentTree, 6, 5, 5)

    • Since left == right, set segmentTree[6] = 1.

  • Set segmentTree[2] = segmentTree[5] + segmentTree[6] = 3.

• Set segmentTree[0] = segmentTree[1] + segmentTree[2] = 6.

After building the segment tree, it looks like this (values represent vacant spots in segments):

[ 6, 3, 3, 2, 1, 2, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Step 4: Place People in the Queue

We'll place each person from the sorted array into their correct position in the resultQueue using the segment tree.

Query to Place [5, 1]:

• Initial Call:

  query(segmentTree, resultQueue, 0, 0, 5, 2, 5, 1)

• Process:

  • Node 0 (root):
    • The current segment is [0, 5].
    • The segment tree value is 6 (total vacant spots).
    • Check the left child (Node 1, segment [0, 2]).
    • Since segmentTree[1] (3) is greater than or equal to position (2), go to the left child.
  • Node 1:
    • The current segment is [0, 2].
    • The segment tree value is 3.
    • Check the left child (Node 3, segment [0, 1]).
    • Since segmentTree[3] (2) is greater than or equal to position (2), go to the left child.
  • Node 3:
    • The current segment is [0, 1].
    • The segment tree value is 2.
    • Check the left child (Node 7, segment [0, 0]). It is 1 < position(2). So, go to the right child.
    • Check the right child (Node 8, segment [1, 1]).
    • Since segmentTree[8] (1) is equal to position (2) - segmentTree[7] (1), go to the right child.
  • Node 8 (leaf):
    • The current segment is [1, 1].
    • The segment tree value is 1.
    • Place [5, 1] at index 1 in resultQueue.
    • Update segmentTree[8] to 0.

• Update Segment Tree:

  • Update the parent nodes to reflect the reduced number of vacant spots.
  • segmentTree = [5, 2, 3, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

• Update resultQueue:

  • resultQueue = [null, [5, 1], null, null, null, null]

Query to Place [5, 0]:

• Initial Call:

  query(segmentTree, resultQueue, 0, 0, 5, 1, 5, 0)

• Process:

  • Node 0 (root):
    • The current segment is [0, 5].
    • The segment tree value is 5.
    • Check the left child (Node 1, segment [0, 2]).
    • Since segmentTree[1] (2) is greater than or equal to position (1), go to the left child.
  • Node 1:
    • The current segment is [0, 2].
    • The segment tree value is 2.
    • Check the left child (Node 3, segment [0, 1]).
    • Since segmentTree[3] (1) is greater than or equal to position (1), go to the left child.
  • Node 3:
    • The current segment is [0, 1].
    • The segment tree value is 1.
    • Check the left child (Node 7, segment [0, 0]).
    • Since segmentTree[7] (1) is equal to position (1), go to the left child.
  • Node 7 (leaf):
    • The current segment is [0, 0].
    • The segment tree value is 1.
    • Place [5, 0] at index 0 in resultQueue.
    • Update segmentTree[7] to 0.

• Update Segment Tree:

  • Update the parent nodes to reflect the reduced number of vacant spots.
  • segmentTree = [4, 1, 3, 0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

• Update resultQueue:

  • resultQueue = [[5, 0], [5, 1], null, null, null, null]

Query to Place [6, 2]:

• query(segmentTree, resultQueue, 0, 0, 5, 3, 6, 2)
  • Traverse the tree:
    • Node 0 (root), right child can accommodate, go right.
    • Node 2, left child can accommodate, go left.
    • Node 5, right child can accommodate, go right.
    • Node 12 (leaf), place [6, 2] at index 4.
  • Update segmentTree and resultQueue:
    • segmentTree = [3, 1, 2, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    • resultQueue = [[5, 0], [5, 1], null, null, [6, 2], null]

Query to Place [6, 0]:

• query(segmentTree, resultQueue, 0, 0, 5, 1, 6, 0)
  • Traverse the tree:
    • Node 0 (root), left child can accommodate, go left.
    • Node 1, right child can accommodate, go right.
    • Node 4 (leaf), place [6, 0] at index 2.
  • Update segmentTree and resultQueue:
    • segmentTree = [2, 0, 2, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    • resultQueue = [[5, 0], [5, 1], [6, 0], null, [6, 2], null]

Query to Place [7, 1]:

• query(segmentTree, resultQueue, 0, 0, 5, 2, 7, 1)
  • Traverse the tree:
    • Node 0 (root), right child can accommodate, go right.
    • Node 2, left child can accommodate, go left.
    • Node 5, left child can accommodate, go left.
    • Node 11 (leaf), place [7, 1] at index 5.
  • Update segmentTree and resultQueue:
    • segmentTree = [1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    • resultQueue = [[5, 0], [5, 1], [6, 0], null, [6, 2], [7, 1]]

Query to Place [7, 0]:

• query(segmentTree, resultQueue, 0, 0, 5, 1, 7, 0)
  • Traverse the tree:
    • Node 0 (root), right child can accommodate, go right.
    • Node 2, right child can accommodate, go right.
    • Node 6 (leaf), place [7, 0] at index 3.
  • Update segmentTree and resultQueue:
    • segmentTree = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    • resultQueue = [[5, 0], [5, 1], [6, 0], [7, 0], [6, 2], [7, 1]]

Final resultQueue after placing all people:

[[5, 0], [5, 1], [6, 0], [7, 0], [6, 2], [7, 1]]

Code

import java.util.*;

class Solution {

  // Build the segment tree
  private static void buildSegmentTree(
    int[] segmentTree,
    int index,
    int left,
    int right
  ) {
    // If it's a leaf node
    if (left == right) {
      segmentTree[index] = 1; // One vacant spot
      return;
    }

    int mid = left + (right - left) / 2;
    buildSegmentTree(segmentTree, 2 * index + 1, left, mid);
    buildSegmentTree(segmentTree, 2 * index + 2, mid + 1, right);

    // Number of vacant spots in the segment
    segmentTree[index] =
      segmentTree[2 * index + 1] + segmentTree[2 * index + 2];
  }

  // Query to place the person at the correct position
  private static void query(
    int[] segmentTree,
    List<int[]> resultQueue,
    int index,
    int left,
    int right,
    int position,
    int height,
    int originalPosition
  ) {
    // If it's a leaf node
    if (left == right) {
      resultQueue.set(left, new int[] { height, originalPosition });
      segmentTree[index]--;
      return;
    }

    // If segment can't accommodate the position
    if (segmentTree[index] < position) return;

    int mid = left + (right - left) / 2;

    // If the left subtree can accommodate the position
    if (segmentTree[2 * index + 1] >= position) {
      query(
        segmentTree,
        resultQueue,
        2 * index + 1,
        left,
        mid,
        position,
        height,
        originalPosition
      );
    } else {
      // If the right subtree needs to be considered
      query(
        segmentTree,
        resultQueue,
        2 * index + 2,
        mid + 1,
        right,
        position - segmentTree[2 * index + 1],
        height,
        originalPosition
      );
    }

    // Reduce the number of vacant spots
    segmentTree[index]--;
  }

  // Reconstruct the queue
  public int[][] reconstructQueue(int[][] people) {
    int n = people.length;
    int[] segmentTree = new int[4 * n];
    List<int[]> resultQueue = new ArrayList<>(Collections.nCopies(n, null));

    // Sort people using custom comparator
    Arrays.sort(people, (a, b) -> {
      if (a[0] == b[0]) {
        return Integer.compare(b[1], a[1]);
      }
      return Integer.compare(a[0], b[0]);
    });

    // Build the segment tree
    buildSegmentTree(segmentTree, 0, 0, n - 1);

    // Place each person in the correct position
    for (int[] person : people) {
      query(
        segmentTree,
        resultQueue,
        0,
        0,
        n - 1,
        person[1] + 1,
        person[0],
        person[1]
      );
    }

    // Convert resultQueue to 2D array
    return resultQueue.toArray(new int[n][2]);
  }

  // Main method to test the algorithm with examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    int[][] example1 = {
      { 6, 0 },
      { 5, 1 },
      { 5, 0 },
      { 7, 0 },
      { 7, 1 },
      { 6, 2 },
    };
    int[][] example2 = { { 4, 0 }, { 5, 1 }, { 7, 0 }, { 6, 1 } };
    int[][] example3 = {
      { 7, 0 },
      { 6, 1 },
      { 5, 2 },
      { 6, 0 },
      { 4, 4 },
      { 5, 1 },
    };

    int[][] result1 = solution.reconstructQueue(example1);
    int[][] result2 = solution.reconstructQueue(example2);
    int[][] result3 = solution.reconstructQueue(example3);

    System.out.println("Example 1: " + Arrays.deepToString(result1));
    System.out.println("Example 2: " + Arrays.deepToString(result2));
    System.out.println("Example 3: " + Arrays.deepToString(result3));
  }
}

Complexity Analysis

Time Complexity

1. Sorting:

   • The sorting step has a time complexity of , where (n) is the number of people.

2. Segment Tree Construction:

   • Building the segment tree takes time because we are initializing an array of size (4n).

3. Query Operations:

   • Each query operation involves traversing the segment tree, which has a time complexity of . Since there are (n) people, the total complexity for all query operations is .

Overall, the time complexity is .

Space Complexity

• The segment tree requires space due to its structure.
• The result array requires space.
• Thus, the total space complexity is .