Queue Reconstruction by Height

LeetCode Q 406 - Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example
Input: [[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]]

Solution

Version 1

Code:

public int[][] reconstructQueue(int[][] people) {

	if (people == null || people.length == 0) return people;

	Arrays.sort(people, (a, b) -> {
		if (a[0] != b[0])
			return b[0] - a[0];
		return a[1] - b[1];
	});

	int[][] res = new int[people.length][2];
	
	for (int i = 0; i < people.length; i++) {
		int pos = people[i][1];
		for (int j = i; j > pos; j--)
			people[j] = people[j - 1];
		res[pos] = people[i];
	}

	return res;
}

Version 2: Sort + Insertion

Code:

public int[][] reconstructQueue(int[][] people) {

	if (people == null || people.length == 0) return people;

	Arrays.sort(people, (a, b) -> {
		if (a[0] != b[0])
			return b[0] - a[0];
		return a[1] - b[1];
	});

	List<int[]> list = new ArrayList<>();

	for (int[] p: people)
		list.add(p[1], p);

	int[][] res = new int[people.length][2];
	int index = 0;

	for (int[] arr: list) {
		res[index++] = arr;
	}
	
	return res;
}