Elements appearing more than n/k times
Problem
Given an array of size n and an integer k, return every element that appears more than n/k times. At most k − 1 elements can qualify.
Example 1
Input: arr = [3, 1, 2, 2, 1, 2, 3, 3], k = 4 Output: [2, 3]
n/k = 2. The values 2 and 3 each appear 3 times.
Also asked as: Given an array of size n and a number k, fin all elements that appear more than " n/k " times
Test cases
Case 1
Input: [3,1,2,2,1,2,3,3], 4 Expected (any order): [2,3]
Case 2
Input: [1,1,2,2,3], 3 Expected (any order): [1,2]
Case 3
Input: [5,5,5,5], 2 Expected (any order): [5]
Case 4
Input: [1,2,3,4], 2 Expected (any order): []
View solutionHide solution1 approach
1. Generalised Boyer–Moore (k−1 counters)
Time O(n · k)Space O(k)
At most k−1 elements can exceed n/k. Keep k−1 candidate/count slots; a final pass verifies the true counts.
function moreThanNK(a, k) { const cnt = new Map(); // up to k-1 entries for (const x of a) { if (cnt.has(x)) cnt.set(x, cnt.get(x) + 1); else if (cnt.size < k - 1) cnt.set(x, 1); else { for (const key of [...cnt.keys()]) { cnt.set(key, cnt.get(key) - 1); if (cnt.get(key) === 0) cnt.delete(key); } } } const res = []; for (const key of cnt.keys()) { if (a.filter((v) => v === key).length > a.length / k) res.push(key); } return res;}