Majority Element

Problem Statement

Given an array arr[], find the majority element in the array.

A majority element is an element that appears strictly more than arr.size()/2 times.
If no majority element exists, return -1.
Examples
Input: arr = [1, 1, 2, 1, 3, 5, 1]
Output: 1

Explanation: 1 appears more than 7/2 = 3.5 times.

Input: arr = [7]
Output: 7

Explanation: Single element is trivially the majority.

Input: arr = [2, 13]
Output: -1

Explanation: No element appears more than 2/2 = 1 times.

Constraints
1 ≤ arr.size() ≤ 10^5
1 ≤ arr[i] ≤ 10^5

Approach 1: Using Hash Map

Count the frequency of each element using a dictionary. If an element count exceeds n//2, return it.

Time Complexity: O(n)
Space Complexity: O(n)

from typing import List

class Solution:
def majorityElement(self, arr: List[int]) -> int:
n = len(arr)
freq = {}

    for num in arr:
        freq[num] = freq.get(num, 0) + 1
        if freq[num] > n // 2:
            return num

    return -1

Approach 2: Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm allows finding a candidate for majority in O(n) time and O(1) space:

Initialize candidate = None and count = 0.
Iterate over the array:
If count == 0, set candidate = num.
If num == candidate, increment count.
Else, decrement count.
After one pass, the candidate may be the majority.
Verify by counting its occurrences.
from typing import List

Python code

class Solution:
def majorityElement(self, arr: List[int]) -> int:
candidate = None
count = 0

    # Phase 1: Find candidate
    for num in arr:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # Phase 2: Verify candidate
    if arr.count(candidate) > len(arr) // 2:
        return candidate
    return -1

How It Works
Phase 1: Identify a candidate that could be the majority by canceling out different elements.
Phase 2: Confirm the candidate is actually the majority.
This method is extremely efficient for large arrays because it uses constant space.

Time Complexity: O(n)
Space Complexity: O(1)