ยท 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.
Learning From
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
Video
https://youtu.be/7KHKFqLPMbsProblem 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
- Blind 75 - Group Anagram Oct 30, 2022
- Blind 75 - Reverse LinkedList Nov 16, 2022
- Blind 75 - Same Tree Nov 16, 2022
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.