DOMINANT2 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Utkarsh Gupta
Preparer: Jeevan Jyot Singh
Testers: Abhinav Sharma, Venkata Nikhil Medam
Editorialist: Nishank Suresh

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')
2 Likes

@codechef_admin new page formate during the contests takes lots of time for loading .Its better to provied old page formate during the contest…