Solution with explanation of the algorithm


  • 1
    L

    If you could spot the pattern that this would require sorting, you're half-done already. However, the bigger part is to sort on what. After you sort, you could solve this problem in two ways albeit with different complexity:

    1. Sort on number of people at ahead and use smaller height in the case of a tie -- Here you will get the values in this order:
      [
      [5,0]
      [7,0]
      [6,1]
      [7,1]
      [5,2]
      [4,4]
      ]

    If you start adding these inside a new list in that order, the cost will be to additional search to find how many numbers that are bigger than the given height are ahead of the one to be added. For example, we would insert [5,0] then [7,0] and now [6,1]. For the last one you need to search and find how many heights that are >=6 are ahead and then you place it accordingly. This will require additional search and it is not optimal.

    1. Sort on the height the reverse way so that biggest is first and the tie is resolved by less people at the front. This will yield :

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

    It is clear that (4,4) has to have 4 people ahead of him/her. Likewise, that is true for all tuples here. So just read each tuple and insert that into a list at an index matching the order (it starts from 0 so we insert at 4 not 5).

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

  • 0

    A very good solution and easy to understand. Thank you.


Log in to reply
 

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