Top K Elements

// LeetCode #347 — Top K Frequent Elements (Bucket Sort)
public int[] topKFrequent(int[] nums, int k) {
    // Step 1: Count frequencies
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums)
        freq.merge(n, 1, Integer::sum);

    // Step 2: Create buckets indexed by frequency
    List<Integer>[] buckets = new List[nums.length + 1];
    for (var entry : freq.entrySet()) {
        int f = entry.getValue();
        if (buckets[f] == null)
            buckets[f] = new ArrayList<>();
        buckets[f].add(entry.getKey());
    }

    // Step 3: Collect from highest frequency down
    int[] result = new int[k];
    int idx = 0;
    for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
        if (buckets[i] != null)
            for (int val : buckets[i])
                if (idx < k) result[idx++] = val;
    }
    return result;
}

// LeetCode #347 — Top K Frequent Elements (Bucket Sort)
func topKFrequent(nums []int, k int) []int {
    // Step 1: Count frequencies
    freq := make(map[int]int)
    for _, n := range nums {
        freq[n]++
    }

    // Step 2: Create buckets indexed by frequency
    buckets := make([][]int, len(nums)+1)
    for val, f := range freq {
        buckets[f] = append(buckets[f], val)
    }

    // Step 3: Collect from highest frequency down
    result := make([]int, 0, k)
    for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
        for _, val := range buckets[i] {
            result = append(result, val)
            if len(result) == k {
                return result
            }
        }
    }
    return result
}

# LeetCode #347 — Top K Frequent Elements (Bucket Sort)
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    # Step 1: Count frequencies
    freq = Counter(nums)

    # Step 2: Create buckets indexed by frequency
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for val, f in freq.items():
        buckets[f].append(val)

    # Step 3: Collect from highest frequency down
    result: list[int] = []
    for i in range(len(buckets) - 1, -1, -1):
        for val in buckets[i]:
            result.append(val)
            if len(result) == k:
                return result
    return result

// LeetCode #347 — Top K Frequent Elements (Bucket Sort)
use std::collections::HashMap;

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

        // Step 2: Create buckets indexed by frequency
        let mut buckets: Vec<Vec<i32>> = vec![vec![]; nums.len() + 1];
        for (&val, &f) in &freq {
            buckets[f].push(val);
        }

        // Step 3: Collect from highest frequency down
        let mut result: Vec<i32> = Vec::new();
        for bucket in buckets.iter().rev() {
            for &val in bucket {
                result.push(val);
                if result.len() == k as usize {
                    return result;
                }
            }
        }
        result
    }
}

// LeetCode #347 — Top K Frequent Elements (Bucket Sort)
function topKFrequent(nums: number[], k: number): number[] {
    // Step 1: Count frequencies
    const freq = new Map<number, number>();
    for (const n of nums)
        freq.set(n, (freq.get(n) ?? 0) + 1);

    // Step 2: Create buckets indexed by frequency
    const buckets: number[][] = new Array(nums.length + 1);
    for (const [val, f] of freq) {
        if (!buckets[f]) buckets[f] = [];
        buckets[f].push(val);
    }

    // Step 3: Collect from highest frequency down
    const result: number[] = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i])
            for (const val of buckets[i])
                if (result.length < k) result.push(val);
    }
    return result;
}

// Template: Top K Elements using Min-Heap
// Finds the k largest elements (or kth largest)

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();   // evict smallest
    }
}

// minHeap.peek() = kth largest element
// Heap contents = top k largest elements
return minHeap.peek();

// Template: Top K Elements using sort.Slice
// Finds the k largest elements (or kth largest)
import "sort"

// Sort descending to bring k largest to the front
sort.Slice(nums, func(i, j int) bool {
    return nums[i] > nums[j]
})

// nums[k-1] = kth largest element
// nums[:k]  = top k largest elements
return nums[k-1]

# Template: Top K Elements using Min-Heap
# Finds the k largest elements (or kth largest)

min_heap: list[int] = []

for num in nums:
    heapq.heappush(min_heap, num)
    if len(min_heap) > k:
        heapq.heappop(min_heap)  # evict smallest

# min_heap[0] = kth largest element
# Heap contents = top k largest elements
return min_heap[0]

// Template: Top K Elements using Min-Heap
// Finds the k largest elements (or kth largest)
use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();

for num in nums {
    min_heap.push(Reverse(num));
    if min_heap.len() > k as usize {
        min_heap.pop();  // evict smallest
    }
}

// min_heap.peek().unwrap().0 = kth largest element
// Heap contents = top k largest elements
min_heap.peek().unwrap().0

// Template: Top K Elements using Min-Heap
// Finds the k largest elements (or kth largest)

const minHeap = new MinPriorityQueue<number>();

for (const num of nums) {
    minHeap.enqueue(num);
    if (minHeap.size() > k) {
        minHeap.dequeue();  // evict smallest
    }
}

// minHeap.front().element = kth largest element
// Heap contents = top k largest elements
return minHeap.front().element;