Java O(N) time and O(N) space method using HashMap and Heap


  • 0
    J
    public class Solution {
        class Pair implements Comparable<Pair> {
            int num;
            int count;
            
            public Pair(int num, int count) {
                this.num = num;
                this.count = count;
            }
            /*Logic to comapre pairs*/
            public int compareTo(Pair p) {
                return p.count - this.count;
            }
        }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            //Collect the count
            HashMap<Integer, Pair> numToCount = new HashMap<>();
            for (int num : nums) {
                if (!numToCount.containsKey(num)) {
                    numToCount.put(num, new Pair(num, 0));
                }
                numToCount.get(num).count += 1;
            }
            /*Find Topk with priorityQueue O(n) time. Constructor: PriorityQueue<>(Collection<T>) 
    calls heapify to build the heap.*/
            Queue<Pair> pq = new PriorityQueue<>(numToCount.values());
            List<Integer> res = new ArrayList<>();
            
            while (k > 0) {
                res.add(pq.poll().num);
                k--;
            }
            return res;
        }
    }
    

    Note: If you build the heap by inserting each pair into an empty predefined heap. The time complexity will be O(nlogn).


Log in to reply
 

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