# Java solution using PriorityQueue and LinkedList

• Instead of using ArrayList for insertion, using LinkedList is more efficient. Here is the discussion of when to use LinkedList over ArrayList on StackOverFlow.

``````public class Solution {
class PairComp implements Comparator<int[]> {
public int compare(int[] p1, int[] p2){
int comp_h = Integer.compare(p2[0], p1[0]);
return comp_h == 0 ? Integer.compare(p1[1], p2[1]): comp_h;
}
}
public int[][] reconstructQueue(int[][] people) {
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(1, new PairComp() );
for (int[] ppl: people){
queue.offer( ppl );
}
while ( ! queue.isEmpty() ) {
int[] pair = queue.poll();
}
int[][] ret = new int[people.length][];
for (int i=0; i<list.size(); i++){
ret[i] = list.get(i);
}
return ret;
}
}
``````

Shorter version without using PriorityQueue:

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
return p1[0]!=p2[0]?Integer.compare(p2[0],p1[0]): Integer.compare(p1[1],p2[1]);
}
});
List<int[]> list = new LinkedList();
for (int[] ppl: people) list.add(ppl[1], ppl);
return list.toArray(new int[people.length][] );
}
}
``````

• This post is deleted!

• what a brilliant idea!!

• What exactly makes you think LinkedList is more efficient than ArrayList? I tried your (second) solution with both, each three times, alternating between the versions:

ArrayList: 17 ms
ArrayList: 19 ms
ArrayList: 15 ms

ArrayList looks like the clear winner to me.

Then I did this to make that second part take more time and thus reduce the impact of the sorting:

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
return p1[0]!=p2[0]?Integer.compare(p2[0],p1[0]): Integer.compare(p1[1],p2[1]);
}
});
List<int[]> list = new LinkedList();
for (int i=0; i<100; i++) {
list = new LinkedList();
for (int[] ppl: people) list.add(ppl[1], ppl);
}
return list.toArray(new int[people.length][] );
}
}
``````

LinkedList: 431 ms, 239 ms, 411 ms
ArrayList: 143 ms, 147 ms, 131 ms

Here ArrayList was the even much clearer winner.

• I agree, linklist is not necessary more efficient than arraylist here.
I think they theoretically equivalent in add(position, item);

for linklist, it take o(n) to get to position;
for arraylist, it take o(n) to move elements after position to the back.(seems like there is a super fast system call to do this)

:) I might be wrong, pls let me know if i am.

• @henry91w I'd say you're right except that they're not o(n) but O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.