Elements appearing more than n/k times

Medium

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}