algoadvance

Leetcode 406. Queue Reconstruction by Height

Problem Statement

You are given an array of people, where people[i] = [hi, ki] represents the ith person having a height of hi and exactly ki other people in front of them who have a height greater than or equal to hi.

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] = [hj, kj] is the attributes of the jth person in the queue.

Example

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

Clarifying Questions

  1. Q: Can there be people with the same height and k-value?
    • A: Yes.
  2. Q: Do the input arrays always contain valid persons?
    • A: Yes. Assume all input is valid as per the problem description.
  3. Q: Is the input guaranteed to be non-empty?
    • A: Yes.

Strategy

To solve this problem, we’ll use a greedy approach by performing the following steps:

  1. Sort the array of people. First, sort by height in descending order. If two people have the same height, sort them by the number of people in front of them (k) in ascending order.
  2. Reconstruct the queue by inserting each person into a new list at the index equal to their k value.

Steps

  1. Sort: Sort the array people using a custom comparator.
  2. Insert: Insert each person into the result list according to their k value.

Code

import java.util.*;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // Sort with custom comparator
        // First by height in descending and then by k value in ascending
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return b[0] - a[0];
            } else {
                return a[1] - b[1];
            }
        });
        
        // Reconstruct the queue
        List<int[]> result = new LinkedList<>();
        for (int[] person : people) {
            result.add(person[1], person);
        }
        
        // Convert list to array
        return result.toArray(new int[people.length][2]);
    }
}

Time Complexity

So, the overall time complexity is (O(n^2)).

Space Complexity

The approach ensures that the people are placed in the correct order, respecting both their height and the number of people in front of them, achieving the desired reconstruction of the queue.

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