Problem

Given an array of size n and a number k, find all elements in the array that appear more than n/k times.

Examples

Example 1

1
2
3

Input: arr = [2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8], k = 4
Output: [3, 4]
Explanation: n = 14, n/k = 3. Elements 3 and 4 appear 5 and 4 times respectively, which is more than 3.

Constraints

  • 1 <= n <= 10^5
  • 2 <= k <= n
  • Array elements are integers (may be negative or positive)

Solution

Method 1 – Brute Force (Nested Loops)

Intuition

Check the count of each element by comparing it with every other element.

Approach

  1. For each element in the array, count its occurrences by scanning the array.
  2. If the count is more than n/k and the element is not already in the answer, add it.
  3. Return the answer list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
  vector<int> findElements(vector<int>& arr, int k) {
    int n = arr.size();
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
      int cnt = 0;
      for (int j = 0; j < n; ++j) if (arr[j] == arr[i]) ++cnt;
      if (cnt > n / k && find(ans.begin(), ans.end(), arr[i]) == ans.end())
        ans.push_back(arr[i]);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func findElements(arr []int, k int) []int {
  n := len(arr)
  ans := []int{}
  for i := 0; i < n; i++ {
    cnt := 0
    for j := 0; j < n; j++ {
      if arr[j] == arr[i] {
        cnt++
      }
    }
    found := false
    for _, v := range ans {
      if v == arr[i] {
        found = true
        break
      }
    }
    if cnt > n/k && !found {
      ans = append(ans, arr[i])
    }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
  public List<Integer> findElements(int[] arr, int k) {
    int n = arr.length;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      int cnt = 0;
      for (int j = 0; j < n; ++j) if (arr[j] == arr[i]) ++cnt;
      if (cnt > n / k && !ans.contains(arr[i]))
        ans.add(arr[i]);
    }
    return ans;
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
  def findElements(self, arr: list[int], k: int) -> list[int]:
    n = len(arr)
    ans: list[int] = []
    for i in range(n):
      cnt = sum(1 for x in arr if x == arr[i])
      if cnt > n // k and arr[i] not in ans:
        ans.append(arr[i])
    return ans

Complexity

  • ⏰ Time complexity: O(n^2), because for each element, we scan the array.
  • 🧺 Space complexity: O(n), for the answer list.

Method 2 – Generalized Boyer-Moore (Tetris Game Technique)

Intuition

We can have at most k-1 elements that appear more than n/k times. Track up to k-1 candidates and their counts, and reduce counts when the candidate list is full.

Approach

  1. Create a map or array to store up to k-1 candidate elements and their counts.
  2. For each element:
    • If it is already a candidate, increment its count.
    • If there is room, add it as a new candidate with count 1.
    • If no room, decrement the count of all candidates by 1.
  3. After the first pass, count the actual occurrences of each candidate in the array.
  4. Return those with count > n/k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <unordered_map>
class Solution {
public:
  vector<int> findElements(vector<int>& arr, int k) {
    int n = arr.size();
    unordered_map<int, int> counter;
    for (int x : arr) {
      if (counter.count(x)) counter[x]++;
      else if (counter.size() < k-1) counter[x] = 1;
      else for (auto it = counter.begin(); it != counter.end(); )
        if (--(it->second) == 0) it = counter.erase(it); else ++it;
    }
    unordered_map<int, int> actual;
    for (int x : arr) if (counter.count(x)) actual[x]++;
    vector<int> ans;
    for (auto& [num, _] : counter)
      if (actual[num] > n / k) ans.push_back(num);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func findElements(arr []int, k int) []int {
  n := len(arr)
  counter := map[int]int{}
  for _, x := range arr {
    if _, ok := counter[x]; ok {
      counter[x]++
    } else if len(counter) < k-1 {
      counter[x] = 1
    } else {
      for key := range counter {
        counter[key]--
        if counter[key] == 0 {
          delete(counter, key)
        }
      }
    }
  }
  actual := map[int]int{}
  for _, x := range arr {
    if _, ok := counter[x]; ok {
      actual[x]++
    }
  }
  ans := []int{}
  for num := range counter {
    if actual[num] > n/k {
      ans = append(ans, num)
    }
  }
  return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
class Solution {
  public List<Integer> findElements(int[] arr, int k) {
    int n = arr.length;
    Map<Integer, Integer> counter = new HashMap<>();
    for (int x : arr) {
      if (counter.containsKey(x)) counter.put(x, counter.get(x) + 1);
      else if (counter.size() < k-1) counter.put(x, 1);
      else {
        Iterator<Map.Entry<Integer, Integer>> it = counter.entrySet().iterator();
        while (it.hasNext()) {
          Map.Entry<Integer, Integer> entry = it.next();
          int c = entry.getValue() - 1;
          if (c == 0) it.remove();
          else entry.setValue(c);
        }
      }
    }
    Map<Integer, Integer> actual = new HashMap<>();
    for (int x : arr) if (counter.containsKey(x)) actual.put(x, actual.getOrDefault(x, 0) + 1);
    List<Integer> ans = new ArrayList<>();
    for (int num : counter.keySet())
      if (actual.get(num) > n / k) ans.add(num);
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
  def findElements(self, arr: list[int], k: int) -> list[int]:
    n = len(arr)
    counter: dict[int, int] = {}
    for x in arr:
      if x in counter:
        counter[x] += 1
      elif len(counter) < k-1:
        counter[x] = 1
      else:
        for key in list(counter.keys()):
          counter[key] -= 1
          if counter[key] == 0:
            del counter[key]
    actual: dict[int, int] = {}
    for x in arr:
      if x in counter:
        actual[x] = actual.get(x, 0) + 1
    ans: list[int] = []
    for num in counter:
      if actual.get(num, 0) > n // k:
        ans.append(num)
    return ans

Complexity

  • ⏰ Time complexity: O(nk), since each element may cause up to k-1 decrements.
  • 🧺 Space complexity: O(k), for the candidate map.