Java O(N * logN) , detailed explain

  • 0

    The idea is simple, first sort the array by rules:
    Two people : a,b
    if a[0] > b[0] then a<b;
    if a[0] < b[0] then a>b;
    if a[0] = b[0] then sort by people[1];
    if a[1] > b[1] then a>b;

    for example, input:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    after sort:

    next step, put the people in a list at specified position. Iterate the sorted array, when we pick a people , the people before is higher or equal to that. So we just put it according to the position people[1];

    Here is the code:

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if(people.length == 0) return new int[][]{};
            Arrays.sort(people,new mC());
            //put in a list
            List<int[]> list = new LinkedList<>();
            for (int i =1;i<people.length;i++) {
            //return result
            Iterator iterator = list.iterator();
            int i = 0;
            while (iterator.hasNext()) {
                people[i++] = (int[]);
            return people;
        class  mC implements Comparator<int[]> {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] > o2[0]) return -1;
                else if (o1[0] < o2[0]) return 1;
                else {
                    return o1[1] - o2[1];

  • 0

    I think the complexity of 'list.add' will be O(N^2) in the worst cast, that's to say you insert the element at the first place every time.

  • 0

    @merryChris Agree. Not only for worst case, even for average, it is also O(n^2)

Log in to reply

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