Dominant Element

You are given an array A of length N.

An element X is called dominant if:

• The frequency (count) of X is strictly greater than the frequency of any other element in the array.

Example:

• A=[2,1,4,4,4] → 4 appears 3 times, others appear fewer times → 4 is dominant.

• A=[1,2,2,1] → both 1 and 2 appear 2 times → no dominant element.

Your task: For each test case, check whether any dominant element exists.

Problem Restatement

For each test case:

• You are given an integer N — the length of the array.

• You are given N integers A1, A2, ...., An.

You must determine if there exists some value X such that:

• freq(X) > freq(Y) for all Y != X.

If such an X exists, print "YES", otherwise print "NO".

Input Format:

• First line: Integer T — number of test cases.

• For each test case:

• First line: Integer N — size of array.

• Second line: N space-separated integers A1, A2, ...., An.

Output Format:

• For each test case, print YES if there exists a dominant element, else NO.

(Case insensitive: YES, Yes, yes are all valid.)

Constraints:

• 1 ≤ T ≤ 500

• 1 ≤ N ≤ 1000

• 1 ≤ Ai ≤ N

• Sum of N over all test cases ≤ 2⋅105 (implicit from limits)

Array values are small enough to use a simple frequency array.

Sample:

Input:

4

5

2 2 2 2 2

4

1 2 3 4

4

3 3 2 1

6

1 1 2 2 3 4

Output:

YES

NO

YES

NO

Explanation:

• Test 1: [2, 2, 2, 2, 2]

• 2 appears 5 times, others 0 → 2 is dominant → YES.

• Test 2: [1, 2, 3, 4]

• All elements appear once → no element has strictly higher frequency → NO.

• Test 3: [3, 3, 2, 1]

• freq(3) = 2, freq(2)=1, freq(1)=1 → 3 is strictly more frequent → YES.

• Test 4: [1, 1, 2, 2, 3, 4]

• freq(1)=2, freq(2)=2, others ≤ 1

• Max frequency is 2, but two elements share it → no unique maximum → NO.

Key Idea

We only care about frequencies:

1. Compute frequency of every value in the array.

2. Find:

• fmax = maximum frequency among all elements.

• How many elements achieve this maximum frequency.

Dominant element exists if and only if:

• Exactly one element has frequency fmax
  (i.e., there is a unique maximum), and

• fmax is strictly greater than all others → which is equivalent to uniqueness.

So:

• If only one element has frequency = max frequency → print YES.

• Else → print NO.

Approach

Steps:

For each test case:

1. Read N and array A.

2. Create a frequency array freq of size N+1 (since 1 ≤ Ai ≤ N), initialized to 0.

3. For each A[i], increment freq[A[i]].

4. Find:

• maxFreq = maximum value in freq.

• countMax = number of values v such that freq[v] == maxFreq.

5. If countMax == 1, print YES; else print NO.

Time & Space Complexity:

• Per test case:

• Building frequency: O(N)

• Scanning frequency array: O(N)

• Overall across all tests: O(∑N), which is at most 2⋅105 — efficient.

Space: O(N) per test for frequency array (or smaller with map; but array is faster here).

Pseudocode:

Java code

C code

C++ code

Python code

JavaScript code