BL
U

40. Majority Elements Appearing More Than N/3 Times

Med.

Problem Description

Given an array of NN integers, find all elements that appear strictly more than ⌊N/3⌋\lfloor N/3 \rfloor times.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the qualifying elements in ascending order separated by spaces, or -1 if none exist.

Example 1:
Input:
8
3 2 3 1 2 3 2 3
Output:
2 3
Explanation: N=8, N/3 = 2. 3 appears 4 times, 2 appears 3 times. Both > 2.
Example 2:
Input:
3
1 2 3
Output:
-1
Explanation: Each appears 1 time, which is not strictly greater than 3/3 = 1.
Example 3:
Input:
1
10
Output:
10
Explanation: 10 appears 1 time > 0.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online