Blind 75 - Top K Frequent Elements - IMP

Link

Learning From

NeetCode

Asked at

Amazon Facebook Oracle Apple Microsoft Google Uber Adobe Snapchat Cisco Shopee Bloomberg Indeed ByteDance Tesla Arcesium Twitter Dropbox eBay VMware Netflix tiktok Deloitte

Source

Video

https://youtu.be/7KHKFqLPMbs

Problem and Constraints

Get k numbers repeated most often.

All Approaches and Explanations in English

O(n*log n)

count all numbers. sort. and return top k. Use streams to make it cleaner.

Code, if any

Normal Solution

class Solution {
    private int[] bruteforce(int[] nums, int k) {
        Map<Integer, Integer> counts = new HashMap<>();
        for(int num: nums){ // O(n)
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        return counts.entrySet()
                .stream()
                .sorted(Map.Entry.comparingByValue()) // // O(n * log(n))
                .skip(counts.size() - k)
                .map(Map.Entry::getKey)
                .mapToInt(Integer::intValue)
                .toArray();
    }
    public int[] topKFrequent(int[] nums, int k) {
        return bruteforce(nums, k);
    }
}

Heap Solution O(k*log(n)

Bucket Sort