Skip to content

ยท 1 min read

Blind 75 - Top K Frequent Elements - IMP

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

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

Related posts

Get new posts by email

No spam. Unsubscribe anytime. Or grab the RSS feed.

Mailto-based for now. ButtonDown / ConvertKit can replace this form later.


Comments lazy-load on scroll. Prefer GitHub? Giscus activates once PUBLIC_GISCUS_* env vars are set (see Giscus.astro).

Index

Index

Back to Blog