347. Topk frequent elements

347_solution1_sorting.c

#include <stdlib.h>

typedef struct {
  int val;
  int cnt;
} FreqPair;

static int cmpFreqDesc(const void *a, const void *b) {
  return ((FreqPair *)b)->cnt - ((FreqPair *)a)->cnt;
}

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize) {
  int *keys = (int *)malloc(numsSize * sizeof(int));
  int *counts = (int *)malloc(numsSize * sizeof(int));
  int uniqueCount = 0;

  for (int i = 0; i < numsSize; i++) {
    int found = -1;
    for (int j = 0; j < uniqueCount; j++) {
      if (keys[j] == nums[i]) {
        found = j;
        break;
      }
    }

    if (found == -1) {
      keys[uniqueCount] = nums[i];
      counts[uniqueCount] = 1;
      uniqueCount++;
    } else {
      counts[found]++;
    }
  }

  FreqPair *pairs = (FreqPair *)malloc(uniqueCount * sizeof(FreqPair));
  for (int i = 0; i < uniqueCount; i++) {
    pairs[i].val = keys[i];
    pairs[i].cnt = counts[i];
  }

  qsort(pairs, uniqueCount, sizeof(FreqPair), cmpFreqDesc);

  int *result = (int *)malloc(k * sizeof(int));
  for (int i = 0; i < k; i++)
    result[i] = pairs[i].val;

  free(keys);
  free(counts);
  free(pairs);

  *returnSize = k;
  return result;
}

347_solution2_maxheap.c

#include <stdlib.h>

typedef struct {
  int val;
  int cnt;
} HeapItem;

static void swap(HeapItem *a, HeapItem *b) {
  HeapItem tmp = *a;
  *a = *b;
  *b = tmp;
}

static void siftUp(HeapItem *heap, int i) {
  while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[parent].cnt >= heap[i].cnt)
      break;
    swap(&heap[parent], &heap[i]);
    i = parent;
  }
}

static void siftDown(HeapItem *heap, int size, int i) {
  while (1) {
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < size && heap[left].cnt > heap[largest].cnt)
      largest = left;
    if (right < size && heap[right].cnt > heap[largest].cnt)
      largest = right;
    if (largest == i)
      break;
    swap(&heap[i], &heap[largest]);
    i = largest;
  }
}

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize) {
  int *keys = (int *)malloc(numsSize * sizeof(int));
  int *counts = (int *)malloc(numsSize * sizeof(int));
  int uniqueCount = 0;

  for (int i = 0; i < numsSize; i++) {
    int found = -1;
    for (int j = 0; j < uniqueCount; j++) {
      if (keys[j] == nums[i]) {
        found = j;
        break;
      }
    }

    if (found == -1) {
      keys[uniqueCount] = nums[i];
      counts[uniqueCount] = 1;
      uniqueCount++;
    } else {
      counts[found]++;
    }
  }

  HeapItem *maxHeap = (HeapItem *)malloc(uniqueCount * sizeof(HeapItem));
  int heapSize = 0;
  for (int i = 0; i < uniqueCount; i++) {
    maxHeap[heapSize].val = keys[i];
    maxHeap[heapSize].cnt = counts[i];
    siftUp(maxHeap, heapSize);
    heapSize++;
  }

  int *result = (int *)malloc(k * sizeof(int));
  for (int i = 0; i < k; i++) {
    result[i] = maxHeap[0].val;
    heapSize--;
    maxHeap[0] = maxHeap[heapSize];
    siftDown(maxHeap, heapSize, 0);
  }

  free(keys);
  free(counts);
  free(maxHeap);

  *returnSize = k;
  return result;
}

347_solution3_minheap-k.c

#include <stdlib.h>

typedef struct {
  int val;
  int cnt;
} HeapItem;

static void swap(HeapItem *a, HeapItem *b) {
  HeapItem tmp = *a;
  *a = *b;
  *b = tmp;
}

static void siftUp(HeapItem *heap, int i) {
  while (i > 0) {
    int parent = (i - 1) / 2;
    if (heap[parent].cnt <= heap[i].cnt)
      break;
    swap(&heap[parent], &heap[i]);
    i = parent;
  }
}

static void siftDown(HeapItem *heap, int size, int i) {
  while (1) {
    int smallest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < size && heap[left].cnt < heap[smallest].cnt)
      smallest = left;
    if (right < size && heap[right].cnt < heap[smallest].cnt)
      smallest = right;
    if (smallest == i)
      break;
    swap(&heap[i], &heap[smallest]);
    i = smallest;
  }
}

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize) {
  int *keys = (int *)malloc(numsSize * sizeof(int));
  int *counts = (int *)malloc(numsSize * sizeof(int));
  int uniqueCount = 0;

  for (int i = 0; i < numsSize; i++) {
    int found = -1;
    for (int j = 0; j < uniqueCount; j++) {
      if (keys[j] == nums[i]) {
        found = j;
        break;
      }
    }

    if (found == -1) {
      keys[uniqueCount] = nums[i];
      counts[uniqueCount] = 1;
      uniqueCount++;
    } else {
      counts[found]++;
    }
  }

  HeapItem *minHeap = (HeapItem *)malloc((k + 1) * sizeof(HeapItem));
  int heapSize = 0;

  for (int i = 0; i < uniqueCount; i++) {
    minHeap[heapSize].val = keys[i];
    minHeap[heapSize].cnt = counts[i];
    siftUp(minHeap, heapSize);
    heapSize++;

    if (heapSize > k) {
      heapSize--;
      minHeap[0] = minHeap[heapSize];
      siftDown(minHeap, heapSize, 0);
    }
  }

  int *result = (int *)malloc(heapSize * sizeof(int));
  for (int i = 0; i < heapSize; i++)
    result[i] = minHeap[i].val;

  free(keys);
  free(counts);
  free(minHeap);

  *returnSize = heapSize;
  return result;
}

347_solution4_bucket_sort.c

#include <stdlib.h>

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize) {
  int *keys = (int *)malloc(numsSize * sizeof(int));
  int *counts = (int *)malloc(numsSize * sizeof(int));
  int uniqueCount = 0;

  for (int i = 0; i < numsSize; i++) {
    int found = -1;
    for (int j = 0; j < uniqueCount; j++) {
      if (keys[j] == nums[i]) {
        found = j;
        break;
      }
    }

    if (found == -1) {
      keys[uniqueCount] = nums[i];
      counts[uniqueCount] = 1;
      uniqueCount++;
    } else {
      counts[found]++;
    }
  }

  int **buckets = (int **)calloc(numsSize + 1, sizeof(int *));
  int *bucketSizes = (int *)calloc(numsSize + 1, sizeof(int));
  int *bucketCap = (int *)calloc(numsSize + 1, sizeof(int));

  for (int i = 0; i < uniqueCount; i++) {
    int cnt = counts[i];
    if (bucketSizes[cnt] == bucketCap[cnt]) {
      bucketCap[cnt] = bucketCap[cnt] == 0 ? 4 : bucketCap[cnt] * 2;
      buckets[cnt] = (int *)realloc(buckets[cnt], bucketCap[cnt] * sizeof(int));
    }
    buckets[cnt][bucketSizes[cnt]++] = keys[i];
  }

  int *result = (int *)malloc(k * sizeof(int));
  int idx = 0;
  for (int cnt = numsSize; cnt >= 0 && idx < k; cnt--) {
    for (int j = 0; j < bucketSizes[cnt] && idx < k; j++) {
      result[idx++] = buckets[cnt][j];
    }
  }

  for (int i = 0; i <= numsSize; i++)
    free(buckets[i]);
  free(buckets);
  free(bucketSizes);
  free(bucketCap);
  free(keys);
  free(counts);

  *returnSize = k;
  return result;
}

347_solution1_sorting.cpp

#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> topKFrequent(vector<int> &nums, int k) {
    unordered_map<int, int> freq;
    for (int &n : nums)
      freq[n]++;

    vector<pair<int, int>> v(freq.begin(), freq.end());
    sort(v.begin(), v.end(),
         [](auto &a, auto &b) { return a.second > b.second; });

    vector<int> res;
    for (int i = 0; i < k; i++)
      res.push_back(v[i].first);
    return res;
  }
};

347_solution2_maxheap.cpp

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> topKFrequent(vector<int> &nums, int k) {
    unordered_map<int, int> freq;
    priority_queue<pair<int, int>> pq;
    vector<int> res;

    for (int &n : nums)
      freq[n]++;

    for (auto it : freq)
      pq.push({it.second, it.first});

    for (int i = 0; i < k; i++) {
      res.push_back(pq.top().second);
      pq.pop();
    }

    return res;
  }
};

347_solution3_minheap-k.cpp

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> topKFrequent(vector<int> &nums, int k) {
    unordered_map<int, int> freq;
    for (int &n : nums)
      freq[n]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    for (auto &[val, cnt] : freq) {
      minHeap.push({cnt, val});
      if (minHeap.size() > k)
        minHeap.pop();
    }

    vector<int> res;
    while (!minHeap.empty()) {
      res.push_back(minHeap.top().second);
      minHeap.pop();
    }
    return res;
  }
};

347_solution4_bucket_sort.cpp

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> topKFrequent(vector<int> &nums, int k) {
    unordered_map<int, int> freq;
    for (int &n : nums)
      freq[n]++;

    vector<vector<int>> buckets(nums.size() + 1);
    for (auto &f : freq)
      buckets[f.second].push_back(f.first);

    vector<int> res;
    for (int i = buckets.size() - 1; i >= 0 && (int)res.size() < k; i--) {
      for (int val : buckets[i]) {
        res.push_back(val);
        if ((int)res.size() == k)
          break;
      }
    }

    return res;
  }
};

347_solution1_sorting.go

package main

import "sort"

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, n := range nums {
        freq[n]++
    }

    keys := make([]int, 0, len(freq))
    for key := range freq {
        keys = append(keys, key)
    }

    sort.Slice(keys, func(i, j int) bool { return freq[keys[i]] > freq[keys[j]] })

    return keys[:k]
}

347_solution2_maxheap.go

package main

import "container/heap"

type maxHeapItem struct {
    val, cnt int
}

type MaxHeap []maxHeapItem

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].cnt > h[j].cnt }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(maxHeapItem)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, n := range nums {
        freq[n]++
    }

    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    for val, cnt := range freq {
        heap.Push(maxHeap, maxHeapItem{val, cnt})
    }

    res := make([]int, 0, k)
    for i := 0; i < k; i++ {
        res = append(res, heap.Pop(maxHeap).(maxHeapItem).val)
    }
    return res
}

347_solution3_minheap-k.go

package main

import "container/heap"

type minHeapItem struct {
    val, cnt int
}

type MinHeap []minHeapItem

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].cnt < h[j].cnt }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(minHeapItem)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, n := range nums {
        freq[n]++
    }

    minHeap := &MinHeap{}
    heap.Init(minHeap)
    for val, cnt := range freq {
        heap.Push(minHeap, minHeapItem{val, cnt})
        if minHeap.Len() > k {
            heap.Pop(minHeap)
        }
    }

    res := make([]int, minHeap.Len())
    for i := len(res) - 1; i >= 0; i-- {
        res[i] = heap.Pop(minHeap).(minHeapItem).val
    }
    return res
}

347_solution4_bucket_sort.go

package main

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, n := range nums {
        freq[n]++
    }

    buckets := make([][]int, len(nums)+1)
    for val, cnt := range freq {
        buckets[cnt] = append(buckets[cnt], val)
    }

    res := make([]int, 0, k)
    for i := len(buckets) - 1; i >= 0 && len(res) < k; i-- {
        for _, val := range buckets[i] {
            res = append(res, val)
            if len(res) == k {
                break
            }
        }
    }

    return res
}

347_solution1_sorting.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums)
            freq.merge(n, 1, Integer::sum);

        List<Integer> keys = new ArrayList<>(freq.keySet());
        keys.sort((a, b) -> freq.get(b) - freq.get(a));

        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = keys.get(i);
        return res;
    }
}

347_solution2_maxheap.java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums)
            freq.merge(n, 1, Integer::sum);

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : freq.entrySet())
            maxHeap.offer(new int[] { entry.getValue(), entry.getKey() });

        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = maxHeap.poll()[1];
        return res;
    }
}

347_solution3_minheap-k.java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums)
            freq.merge(n, 1, Integer::sum);

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            minHeap.offer(new int[] { entry.getValue(), entry.getKey() });
            if (minHeap.size() > k)
                minHeap.poll();
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = minHeap.poll()[1];
        return res;
    }
}

347_solution4_bucket_sort.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums)
            freq.merge(n, 1, Integer::sum);

        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++)
            buckets.add(new ArrayList<>());

        for (Map.Entry<Integer, Integer> entry : freq.entrySet())
            buckets.get(entry.getValue()).add(entry.getKey());

        int[] res = new int[k];
        int idx = 0;
        for (int i = buckets.size() - 1; i >= 0 && idx < k; i--) {
            for (int val : buckets.get(i)) {
                res[idx++] = val;
                if (idx == k)
                    break;
            }
        }

        return res;
    }
}

347_solution1_sorting.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const entries = Array.from(freq.entries());
  entries.sort((a, b) => b[1] - a[1]);

  return entries.slice(0, k).map((entry) => entry[0]);
};

347_solution2_maxheap.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const maxHeap = Array.from(freq.entries());
  maxHeap.sort((a, b) => b[1] - a[1]);

  const res = [];
  for (let i = 0; i < k; i++) res.push(maxHeap[i][0]);
  return res;
};

347_solution3_minheap-k.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const minHeap = [];
  for (const [val, cnt] of freq.entries()) {
    minHeap.push([cnt, val]);
    minHeap.sort((a, b) => a[0] - b[0]);
    if (minHeap.length > k) minHeap.shift();
  }

  return minHeap.map((entry) => entry[1]);
};

347_solution4_bucket_sort.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, cnt] of freq.entries()) buckets[cnt].push(val);

  const res = [];
  for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
    for (const val of buckets[i]) {
      res.push(val);
      if (res.length === k) break;
    }
  }

  return res;
};

347_solution1_sorting.py

from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        items = sorted(freq.items(), key=lambda item: item[1], reverse=True)

        return [val for val, _ in items[:k]]

347_solution2_maxheap.py

import heapq
from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        maxHeap = [(-cnt, val) for val, cnt in freq.items()]
        heapq.heapify(maxHeap)

        res = []
        for _ in range(k):
            _, val = heapq.heappop(maxHeap)
            res.append(val)
        return res

347_solution3_minheap-k.py

import heapq
from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        minHeap = []

        for val, cnt in freq.items():
            heapq.heappush(minHeap, (cnt, val))
            if len(minHeap) > k:
                heapq.heappop(minHeap)

        return [val for _, val in minHeap]

347_solution4_bucket_sort.py

from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]

        for val, cnt in freq.items():
            buckets[cnt].append(val)

        res = []
        for i in range(len(buckets) - 1, -1, -1):
            for val in buckets[i]:
                res.append(val)
                if len(res) == k:
                    return res

        return res

347_solution1_sorting.rs

use std::collections::HashMap;

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, i32> = HashMap::new();
        for n in nums {
            *freq.entry(n).or_insert(0) += 1;
        }

        let mut items: Vec<(i32, i32)> = freq.into_iter().collect();
        items.sort_unstable_by(|a, b| b.1.cmp(&a.1));

        items
            .into_iter()
            .take(k as usize)
            .map(|(val, _)| val)
            .collect()
    }
}

347_solution2_maxheap.rs

use std::collections::{BinaryHeap, HashMap};

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, i32> = HashMap::new();
        for n in nums {
            *freq.entry(n).or_insert(0) += 1;
        }

        let mut max_heap: BinaryHeap<(i32, i32)> = BinaryHeap::new();
        for (val, cnt) in freq {
            max_heap.push((cnt, val));
        }

        let mut res = Vec::new();
        for _ in 0..k {
            if let Some((_, val)) = max_heap.pop() {
                res.push(val);
            }
        }
        res
    }
}

347_solution3_minheap-k.rs

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, i32> = HashMap::new();
        for n in nums {
            *freq.entry(n).or_insert(0) += 1;
        }

        let mut min_heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new();
        for (val, cnt) in freq {
            min_heap.push(Reverse((cnt, val)));
            if min_heap.len() > k as usize {
                min_heap.pop();
            }
        }

        min_heap.into_iter().map(|Reverse((_, val))| val).collect()
    }
}

347_solution4_bucket_sort.rs

use std::collections::HashMap;

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, i32> = HashMap::new();
        for n in &nums {
            *freq.entry(*n).or_insert(0) += 1;
        }

        let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); nums.len() + 1];
        for (val, cnt) in freq {
            buckets[cnt as usize].push(val);
        }

        let mut res = Vec::new();
        for bucket in buckets.iter().rev() {
            for &val in bucket {
                res.push(val);
                if res.len() == k as usize {
                    return res;
                }
            }
        }

        res
    }
}