# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Utkarsh Gupta

*Jeevan Jyot Singh*

**Preparer:***Abhinav Sharma, Venkata Nikhil Medam*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1171

# PREREQUISITES:

Frequency tables

# PROBLEM:

Given an array A, report whether it has a dominant element, i.e, an element whose frequency is larger than the frequency of any other element.

# EXPLANATION:

Let M be the maximum frequency of any element in A. Then,

- If there are two or more elements with frequency M, there cannot be a dominant element
- Otherwise, there is a unique element with frequency M, which is a dominant element

To check these cases, all that needs to be done is to know the frequency of every element of A. Note that computing frequencies by iterating across the entire array each time might be too slow, because it can be a complexity of \mathcal{O}(N^2) in the worst case.

Instead, we build the *frequency array* of A. This can be done as follows:

- Let F be our frequency array. Since every element in A lies between 1 and N, it is enough to have F be of length N.
- Initialize F with zeroes.
- Then, for each i from 1 to N, add 1 to F_{A_i}.
- At the end of this, F_x holds the number of times x appears in A.

Now that we have F, we can solve the problem as mentioned in the first step. Let M be the maximum element of F, and then check whether M appears exactly once in F (in which case the answer is â€śYesâ€ť) or more than once (in which case the answer is â€śNoâ€ť).

# TIME COMPLEXITY:

\mathcal{O}(N) per test case.

# CODE:

## Tester (C++)

```
// Tester: Nikhil_Medam
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 1e3 + 5;
int t, n, a[N];
unordered_map<int,int> freq;
int32_t main() {
cin >> t;
while(t--) {
freq.clear();
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
freq[a[i]]++;
}
int max_freq = 0, max_freq_count = 0;
for(auto &i: freq) {
if(i.second > max_freq) {
max_freq = i.second;
max_freq_count = 1;
}
else if(i.second == max_freq) {
max_freq_count++;
}
}
if(max_freq_count == 1) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}
```

## Editorialist (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = [0]*(n+1)
for x in a:
freq[x] += 1
mx = max(freq)
print('yes' if freq.count(mx) == 1 else 'no')
```