Accepted Solution in Java


  • 0
    H

    Approach is simple here:-

    1. Make a hashmap of height to list of indexes at which they should be placed.
    2. Now, starting forming the result from tallest ones to shortest ones. The reason to do this is that when we insert shorter ones, it will never affect the order of longer ones in the queue present already even if they change their indexes.
    public class Solution {
    
      public int[][] reconstructQueue(int[][] people) {
        TreeMap<Integer, List<Integer>> map = new TreeMap<>(
            new Comparator<Integer>() {
                @Override
                public int compare(Integer e1,
                        Integer e2) {
                    return e2 - e1;
                }
            });
        
        for(int i=0;i<people.length;i++) {
            int h = people[i][0];
            int k = people[i][1];
            if(map.get(h) == null) {
                map.put(h, new ArrayList<>());
            }
            
            map.get(h).add(k);
        }
        
        List<int[]> result = new ArrayList<>();
        for(Integer height : map.keySet()) {
            List<Integer> positions = map.get(height);
            Collections.sort(positions);
            
            for(Integer pos : positions) {
                int[] r = new int[2];
                r[0] = height;
                r[1] = pos;
                result.add(pos, r);
            }
        }
        
        int[][] res = new int[people.length][2];
        int i =0;
        for(int[] key : result) {
            res[i][0] = key[0];
            res[i++][1] = key[1];
        }
        return res;
    }
    

    }


Log in to reply
 

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