BL
U

39. Majority Element (> N/2 Times)

Easy

Problem Description

Given an array of NN integers, find the majority element that appears strictly more than ⌊N/2⌋\lfloor N/2 \rfloor times. If no such element exists, print -1.

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 majority element, or -1.

Example 1:
Input:
7
2 2 1 1 1 2 2
Output:
2
Explanation: Element 2 appears 4 times > 7/2 = 3.
Example 2:
Input:
4
1 2 3 4
Output:
-1
Explanation: No element appears more than 2 times.
Example 3:
Input:
1
42
Output:
42
Explanation: 42 appears 1 time > 0.5.
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