Question

Formatted question description: https://leetcode.ca/all/347.html

347. Top K Frequent Elements

Level

Medium

Description

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(*n* log *n*), where n is the array’s size.

Solution

Similar to 692-Top-K-Frequent-Words

To achieve an algorithm with a time complexity better than O(n log n), we can leverage mappings. This approach yields a time complexity of O(n log k).

The strategy involves the use of two maps:

The first map is a hash map that keeps track of each number and its corresponding count.
The second map is a tree map, which organizes each count and the numbers associated with that count. The key distinction here is that the tree map sorts its keys.

Implementation Steps

Counting Occurrences: Iterate over the nums array to tally the occurrence of each number. Store this information in the first map, with the numbers as keys and their counts as values.
Organizing Counts: Process the entries of the first map to compile each count and the associated numbers. Insert these into the second map, ensuring that the counts (keys) are in descending order. This setup enables us to efficiently access numbers based on their frequency.
Selecting Top Frequencies: Traverse the second map to extract the k most frequent elements. This step is streamlined by the descending order of counts in the map.

Consideration

A potential complication arises in situations of frequency ties. The solution must account for how to prioritize numbers when multiple values share the same count. This clarification impacts the selection of the k most frequent elements, especially when the exact ordering or choice of elements within tied groups influences the outcome.

Code

import java.util.*;

public class Top_K_Frequent_Elements {

    // ref: https://leetcode.com/problems/top-k-frequent-elements/solution/

    class Solution_official_oN {
        int[] unique;
        Map<Integer, Integer> count;

        public void swap(int a, int b) {
            int tmp = unique[a];
            unique[a] = unique[b];
            unique[b] = tmp;
        }

        public int partition(int left, int right, int pivot_index) {
            int pivot_frequency = count.get(unique[pivot_index]);
            // 1. move pivot to end
            swap(pivot_index, right);
            int store_index = left;

            // 2. move all less frequent elements to the left
            for (int i = left; i <= right; i++) {
                if (count.get(unique[i]) < pivot_frequency) {
                    swap(store_index, i);
                    store_index++;
                }
            }

            // 3. move pivot to its final place
            swap(store_index, right);

            return store_index;
        }

        public void quickselect(int left, int right, int k_smallest) {
        /*
        Sort a list within left..right till kth less frequent element
        takes its place.
        */

            // base case: the list contains only one element
            if (left == right) return;

            // select a random pivot_index
            Random random_num = new Random();
            int pivot_index = left + random_num.nextInt(right - left);

            // find the pivot position in a sorted list
            pivot_index = partition(left, right, pivot_index);

            // if the pivot is in its final sorted position
            if (k_smallest == pivot_index) {
                return;
            } else if (k_smallest < pivot_index) {
                // go left
                quickselect(left, pivot_index - 1, k_smallest);
            } else {
                // go right
                quickselect(pivot_index + 1, right, k_smallest);
            }
        }

        public int[] topKFrequent(int[] nums, int k) {
            // build hash map : character and how often it appears
            count = new HashMap<>();
            for (int num: nums) {
                count.put(num, count.getOrDefault(num, 0) + 1);
            }

            // array of unique elements
            int n = count.size();
            unique = new int[n];
            int i = 0;
            for (int num: count.keySet()) {
                unique[i] = num;
                i++;
            }

            // kth top frequent element is (n - k)th less frequent.
            // Do a partial sort: from less frequent to the most frequent, till
            // (n - k)th less frequent element takes its place (n - k) in a sorted array.
            // All element on the left are less frequent.
            // All the elements on the right are more frequent.
            quickselect(0, n - 1, n - k);
            // Return top k frequent elements
            return Arrays.copyOfRange(unique, n - k, n);
        }
    }

    class Solution_optimize {
        public int[] topKFrequent(int[] nums, int k) {
            // O(1) time
            if (k == nums.length) {
                return nums;
            }

            // 1. build hash map : character and how often it appears
            // O(N) time
            Map<Integer, Integer> countMap = new HashMap();
            for (int n: nums) {
                countMap.put(n, countMap.getOrDefault(n, 0) + 1);
            }

            // init heap 'the less frequent element first', poll到最后剩下K个最大的
            Queue<Integer> heap = new PriorityQueue<>(
                (n1, n2) -> countMap.get(n1) - countMap.get(n2));

            // 2. keep k top frequent elements in the heap
            // O(N log k) < O(N log N) time
            for (int n: countMap.keySet()) {
                heap.add(n);
                if (heap.size() > k) heap.poll();
            }

            // 3. build an output array
            // O(k log k) time
            int[] top = new int[k];
            for(int i = k - 1; i >= 0; --i) {
                top[i] = heap.poll();
            }
            return top;
        }
    }

    // use an array to save numbers into different bucket whose index is the frequency
    public class Solution_bucketCount {
        public List<Integer> topKFrequent(int[] nums, int k) {

            List<Integer> result = new LinkedList<>();

            if (nums == null || nums.length == 0) {
                return result;
            }

            Map<Integer, Integer> hm = new HashMap<>();
            for(int n: nums){
                hm.put(n, hm.getOrDefault(n, 0) + 1);
            }

            // @note: corner case: if there is only one number in nums, we need the bucket has index 1.
            LinkedList[] bucket = new LinkedList[nums.length + 1];

            for(int n: hm.keySet()){
                int freq = hm.get(n);
                if(bucket[freq] == null) {
                    bucket[freq] = new LinkedList<>();
                }
                bucket[freq].add(n);
            }

            for(int i = bucket.length - 1; i > 0 && k > 0; i--){

                // @note: possible tie happening
                if(bucket[i] != null){
                    List<Integer> list = bucket[i];
                    result.addAll(list);
                    k-= list.size();
                }
            }

            return result;
        }
    }


    class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {

            List<Integer> result = new ArrayList<>();

            if (nums == null || nums.length == 0) {
                return result;
            }

            // from num, to its count
            HashMap<Integer, Integer> hm = new HashMap<>();

            // to store top k
            PriorityQueue<Pair> heap = new PriorityQueue<>(
                (o1, o2) -> (o1.count - o2.count)
            );

            for (int each: nums) {
                hm.put(each, 1 + hm.getOrDefault(each, 0));
            }

            for (Map.Entry<Integer, Integer> entry: hm.entrySet()) {
                heap.offer(new Pair(entry.getKey(), entry.getValue()));

                // @note: i missed it
                if (heap.size() > k) {
                    heap.poll();
                }
            }

            while (!heap.isEmpty()) {
                result.add(heap.poll().num);
            }

            Collections.reverse(result);

            return result;
        }
    }

    class Pair{
        int num;
        int count;
        public Pair(int num, int count){
            this.num=num;
            this.count=count;
        }
    }
}



//////

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Long> frequency = Arrays.stream(nums).boxed().collect(
            Collectors.groupingBy(Function.identity(), Collectors.counting()));
        Queue<Map.Entry<Integer, Long>> queue = new PriorityQueue<>(Map.Entry.comparingByValue());
        for (var entry : frequency.entrySet()) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.stream().mapToInt(Map.Entry::getKey).toArray();
    }
}

// OJ: https://leetcode.com/problems/top-k-frequent-elements/
// Time: O(N + U) on average, O(N + U^2) in the worst case
// Space: O(U)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& A, int k) {
        if (A.size() == k) return A;
        unordered_map<int, int> cnt;
        for (int n : A) cnt[n]++;
        vector<int> ans;
        for (auto &[n, c] : cnt) ans.push_back(n);
        if (ans.size() == k) return ans;
        auto partition = [&](int L, int R) {
            int i = L, j = L, pivotIndex = L + rand() % (R - L + 1), pivot = cnt[ans[pivotIndex]];
            swap(ans[pivotIndex], ans[R]);
            for (; i < R; ++i) {
                if (cnt[ans[i]] > pivot) swap(ans[i], ans[j++]);
            }
            swap(ans[j], ans[R]);
            return j;
        };
        auto quickSelect = [&](int k) {
            int L = 0, R = ans.size() - 1;
            while (L < R) {
                int M = partition(L, R);
                if (M + 1 == k) break;
                if (M + 1 > k) R = M - 1;
                else L = M + 1;
            }
        };
        quickSelect(k);
        ans.resize(k);
        return ans;
    }
};

'''
>>> nums = ["a", "a", "b", "c", "c"]

>>> cnt = Counter(nums)
>>> cnt
Counter({'a': 2, 'c': 2, 'b': 1})

# default to keys
>>> sorted_freqs = sorted(cnt, key=lambda x: (-cnt[x], x))
>>> sorted_freqs
['a', 'c', 'b']
'''
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count the frequency of each element in the list
        cnt = Counter(nums)

        # Sort the elements by frequency in decreasing order
        # diff from below solution: sorted(cnt), not sorted(cnt.items())
        #   more in https://leetcode.ca/2017-10-22-692-Top-K-Frequent-Words/
        sorted_freqs = sorted(cnt, key=lambda x: (-cnt[x], x))

        return sorted_freqs[:k]

##############

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count the frequency of each element in the list
        freqs = Counter(nums)

        # Sort the elements by frequency in decreasing order
        sorted_freqs = sorted(freqs.items(), key=lambda x: x[1], reverse=True)
        # also passing OJ: sorted_freqs = sorted(freqs.items(), key=lambda x: -x[1])

        # Take the top k elements
        top_k = [num for num, freq in sorted_freqs[:k]]

        return top_k

##############

'''
>>> from heapq import heappush
>>> h = []
>>> heappush(h, (3,1))
>>> heappush(h, (1,1))
>>> heappush(h, (2,1))
>>> h
[(1, 1), (3, 1), (2, 1)]

>>> from heapq import heappop
>>> heappop(h)
(1, 1)
>>> heappop(h)
(2, 1)
>>> heappop(h)
(3, 1)
'''

from collections import Counter

class Solution: # heap
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        hp = []
        for num, freq in cnt.items():
            heappush(hp, (freq, num)) # freq first, default sort by 1st element
            if len(hp) > k:
                heappop(hp)
        return [v[1] for v in hp]

##############

from typing import List
import random
# O(n log(n)) in the average case
# O(n^2) worst case
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_map = {}
        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1

        freq_list = list(freq_map.items())
        self.quick_select(freq_list, 0, len(freq_list) - 1, k)

        return [num for num, freq in freq_list[:k]]

    def quick_select(self, freq_list, start, end, k):
        if start == end:
            return

        pivot_idx = random.randint(start, end)
        pivot_freq = freq_list[pivot_idx][1]

        left = start
        right = end

        while left <= right:
            while freq_list[left][1] > pivot_freq:
                left += 1
            while freq_list[right][1] < pivot_freq:
                right -= 1

            if left <= right:
                freq_list[left], freq_list[right] = freq_list[right], freq_list[left]
                left += 1
                right -= 1

        if k <= right:
            self.quick_select(freq_list, start, right, k)
        elif k >= left:
            self.quick_select(freq_list, left, end, k)


###########


'''
>>> x = [1, 2, 3]
>>> x.append([4, 5])
>>> print(x)
[1, 2, 3, [4, 5]]


>>> x = [1, 2, 3]
>>> x.extend([4, 5])
>>> print(x)
[1, 2, 3, 4, 5]
'''
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)

        # not always filled, max possible frequency is len(nums) [1,1,1,1,...]
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in freq.items():
            buckets[freq].append(num)

        res = []
        for bucket in reversed(buckets):
            if bucket:
                res.extend(bucket)
                if len(res) >= k:
                    break

        return res[:k]

############

class Solution(object):
  def topKFrequent(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    d = {}
    res = []
    ans = []
    buckets = [[] for _ in range(len(nums) + 1)]

    for num in nums:
      d[num] = d.get(num, 0) + 1

    for key in d:
      res.append((d[key], key))

    for t in res:
      freq, key = t
      buckets[freq].append(key)

    buckets.reverse()

    for item in buckets:
      if item and k > 0:
        while item and k > 0:
          ans.append(item.pop())
          k -= 1
        if k == 0:
          return ans

    return ans

func topKFrequent(nums []int, k int) []int {
	cnt := map[int]int{}
	for _, v := range nums {
		cnt[v]++
	}
	h := hp{}
	for v, freq := range cnt {
		heap.Push(&h, pair{v, freq})
		if len(h) > k {
			heap.Pop(&h)
		}
	}
	ans := make([]int, k)
	for i := range ans {
		ans[i] = heap.Pop(&h).(pair).v
	}
	return ans
}

type pair struct{ v, cnt int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].cnt < h[j].cnt }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

function topKFrequent(nums: number[], k: number): number[] {
    let hashMap = new Map();
    for (let num of nums) {
        hashMap.set(num, (hashMap.get(num) || 0) + 1);
    }
    let list = [...hashMap];
    list.sort((a, b) => b[1] - a[1]);
    let ans = [];
    for (let i = 0; i < k; i++) {
        ans.push(list[i][0]);
    }
    return ans;
}

use std::collections::HashMap;
impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut map = HashMap::new();
        let mut max_count = 0;
        for &num in nums.iter() {
            let val = map.get(&num).unwrap_or(&0) + 1;
            map.insert(num, val);
            max_count = max_count.max(val);
        }
        let mut k = k as usize;
        let mut res = vec![0; k];
        while k > 0 {
            let mut next = 0;
            for key in map.keys() {
                let val = map[key];
                if val == max_count {
                    res[k - 1] = *key;
                    k -= 1;
                } else if val < max_count {
                    next = next.max(val);
                }
            }
            max_count = next;
        }
        res
    }
}

347 - Top K Frequent Elements

Question

347. Top K Frequent Elements

Level

Description

Solution

Implementation Steps

Consideration

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

347. Top K Frequent Elements

Level

Description

Solution

Implementation Steps

Consideration

Code

All Problems

All Solutions