Heap

top K frequent elements

note that,

first approach is to use PriorityQueue to solve this problem,

class Solution {
    private class Tuple{
        private int num;
        private int freq;

        public Tuple(int num, int freq) {
            this.num = num;
            this.freq = freq;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;

        // use hashmap to store the num itself and its frequency 
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int num = nums[i];
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // use priority queue to reorder those tuple 
        PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(new Comparator<Tuple>(){
            public int compare(Tuple a, Tuple b) {
                return Integer.compare(b.freq, a.freq);
            }
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new Tuple(entry.getKey(), entry.getValue()));
        }

        // output the top k tuple and put them into the list.
        for (int i = 0; i < k && !pq.isEmpty(); i++) {
            res.add(pq.poll().num);
        }
        return res;
    }
}

second approach is to use bucket sort

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // bucket sort
        List<Integer>[] buckets = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int freq = entry.getValue();
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<Integer>();
            }
            buckets[freq].add(entry.getKey());
        }

        for (int i = buckets.length - 1; i >= 0 && k > 0; i--) {
            if (buckets[i] != null) {
                for (int num : buckets[i]) {
                    res.add(num);
                    k--;
                }
            }
        }
        return res;
    }
}

Most frequent subtree sum

for the problems which require the most frequent element, we don't need pq. we can use hashmap and one max variable, it's enough.

class Solution {
    Map<Integer, Integer> map;
    int max = 0;
    public int[] findFrequentTreeSum(TreeNode root) {
        // get the substree sum 
        // pq store cell, sum, occurrance....
        map = new HashMap<>();
        int sum = getSubtreeSum(root);

        LinkedList<Integer> list = new LinkedList<>();
        for (Integer key : map.keySet()) {
            if (map.get(key) == max) {
                list.add(key);
            }
        }

        int[] res = new int[list.size()];
        for(int i = 0; i < res.length; ++i) {
            res[i] = list.get(i);
        }
        return res;
    }

    public int getSubtreeSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = root.val;
        sum += getSubtreeSum(root.left);
        sum += getSubtreeSum(root.right);

        map.put(sum, map.getOrDefault(sum, 0) + 1);

        max = Math.max(max, map.get(sum));

        return sum;
    }
}