Queue Reconstruction By Height

                                            
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        
        vector<vector<int>> res;
        for (const auto& p : people) {
            res.insert(res.begin() + p[1], p);
        }
        
        return res;
    }
};

                                            
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new ArrayList<>();
        for (int[] person : people) {
            result.add(person[1], person);
        }
        return result.toArray(new int[people.length][]);
    }
}

                                            
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key=lambda x: (-x[0], x[1]))
        result = []
        for p in people:
            result.insert(p[1], p)
        return result

                                            
public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (a, b) =>
        {
            if (a[0] != b[0])
            {
                return b[0] - a[0];
            }
            else
            {
                return a[1] - b[1];
            }
        });
        
        List<int[]> result = new List<int[]>();
        
        foreach (var p in people)
        {
            result.Insert(p[1], p);
        }
        
        return result.ToArray();
    }
}

                                            
/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    people.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        } else {
            return b[0] - a[0];
        }
    });
    
    let result = [];
    for (let i = 0; i < people.length; i++) {
        result.splice(people[i][1], 0, people[i]);
    }
    
    return result;
};

                                            
function reconstructQueue(people: number[][]): number[][] {
    people.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
    
    const result: number[][] = [];
    for (const p of people) {
        result.splice(p[1], 0, p);
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[][] $people
     * @return Integer[][]
     */
    function reconstructQueue($people) {
        usort($people, function($a, $b) {
            if ($a[0] == $b[0]) {
                return $a[1] - $b[1];
            }
            return $b[0] - $a[0];
        });
        
        $result = [];
        foreach ($people as $p) {
            array_splice($result, $p[1], 0, [$p]);
        }
        
        return $result;
    }
}

                                            
class Solution {
    func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
        let sortedPeople = people.sorted { a, b in
            if a[0] == b[0] {
                return a[1] < b[1]
            } else {
                return a[0] > b[0]
            }
        }
        
        var result = [[Int]]()
        
        for person in sortedPeople {
            result.insert(person, at: person[1])
        }
        
        return result
    }
}

                                            
class Solution {
    fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
        val sortedPeople = people.sortedWith(compareBy({ -it[0] }, { it[1] }))
        val result = mutableListOf<IntArray>()
        for (person in sortedPeople) {
            result.add(person[1], person)
        }
        return result.toTypedArray()
    }
}

                                            
class Solution {
  List<List<int>> reconstructQueue(List<List<int>> people) {
    people.sort((a, b) {
      if (a[0] != b[0]) {
        return b[0] - a[0];
      } else {
        return a[1] - b[1];
      }
    });

    List<List<int>> result = [];
    for (var p in people) {
      result.insert(p[1], p);
    }

    return result;
  }
}

                                            
func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool {
        a, b := people[i], people[j]
        return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1])
    })

    result := make([][]int, 0)
    for _, p := range people {
        result = append(result, p)
        copy(result[p[1]+1:], result[p[1]:])
        result[p[1]] = p
    }

    return result
}

                                            
# @param {Integer[][]} people
# @return {Integer[][]}
def reconstruct_queue(people)
    people.sort! { |a, b| a[0] == b[0] ? a[1] - b[1] : b[0] - a[0] }
    
    result = []
    people.each { |p| result.insert(p[1], p) }
    
    return result
end

                                            
object Solution {
    def reconstructQueue(people: Array[Array[Int]]): Array[Array[Int]] = {
        val sortedPeople = people.sortWith((a, b) => {
            if (a(0) == b(0)) a(1) < b(1)
            else a(0) > b(0)
        })
        var result = List.empty[Array[Int]]
        for (person <- sortedPeople) {
            result = result.take(person(1)) ++ Array(person) ++ result.drop(person(1))
        }
        result.toArray
    }
}

                                            
impl Solution {
    pub fn reconstruct_queue(people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut people = people;
        people.sort_by(|a, b| {
            if a[0] != b[0] {
                b[0].cmp(&a[0])
            } else {
                a[1].cmp(&b[1])
            }
        });
        
        let mut result = Vec::new();
        for p in people {
            result.insert(p[1] as usize, p);
        }
        
        result
    }
}

To solve this coding challenge, we need to reconstruct a queue based on a list of people, where each person is represented by a pair of numbers \([h_i, k_i]\). Here, \(h_i\) represents the height of the person and \(k_i\) represents the number of people in front of this person who have a height greater than or equal to \(h_i\). The solution involves sorting and then inserting each person into the correct position in the queue.

# Explanation

The primary insight to solve this problem involves sorting the people by height in descending order and then by the number of people in front of them (k-value) in ascending order. This sorting ensures that when we insert each person into the queue, the height conditions are always fulfilled because we place the taller people first.

Detailed Steps in Pseudocode

Sort the array : First, we sort the array of people. We sort by descending height and for people of the same height, by ascending k-value.

This ensures that, at each step of the insertion process, all "taller" people have already been positioned in the queue.

Inject people into the queue : We sequentially insert each person into a new queue based on their k-value. The k-value directly gives the position in the queue where the person should be inserted. Since the people with greater height are already positioned, this guarantees that the k conditions are maintained.

Pseudocode Explanation with Comments

Here is the pseudocode with comments explaining each step:

                                            
# Define the function to reconstruct the queue
# Input: people - List of tuples where each tuple contains a height and a k-value
# Output: reconstructed_queue - The resultant queue reconstructed based on the given rules
function reconstructQueue(people):

# Step 1: Sort the people list
# Sort by height in descending order and by k-value in ascending order for people with same height
people.sort( sort by -height and then by k_value )

# Initialize an empty list to hold the reconstructed queue
reconstructed_queue = []

# Step 2: Insert each person into the ouput list:
for person in people:
# The position to insert the person in the reconstructed_queue is given by the k-value
# Insert the person at the index defined by their k-value
insert person at index person[1] in reconstructed_queue

# Return the reconstructed queue
return reconstructed_queue

Detailed Step-by-Step Explanation

Sort the People List :

* **Why Descending Height**: By sorting by height in descending order, we ensure that when we place each person, all the "taller" and "equal height" people that need to be in front of this person are already considered.

* **Why Ascending k-value**: Sorting by k-value in ascending order for people with the same height ensures that we place a person in the first available valid position relative to people of the same height.

Insert into the Queue :

* Starting with an empty result list (reconstructed_queue), we iterate over the sorted list of people.

* For each person, we directly insert them into the index equal to their k-value. This is because the k-value represents how many people of greater or equal height should be in front of them, and since we've already sorted by height, this insert operation correctly maintains the queue order.

Example Walkthrough

Consider the example input:

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

. * After sorting, we would get:

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

. * Insert each person one by one into the list

reconstructed_queue

based on their k-value.

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

Finally, the reconstructed queue is

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

, matching the expected output.