Majority Element

Majority Element
Problem Statement

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

A majority element is an element that appears more than n/2 times in the array.

If no such element exists, return -1.

Examples
Input: [1, 1, 2, 1, 3, 5, 1]
Output: 1

Input: [2, 13]
Output: -1
Understanding Majority Element

If an element appears more than n/2 times, then:

There can be only one majority element

It will dominate the array

Example:

Array size = 7
n/2 = 3.5
Majority element must appear ≥ 4 times
Approach 1: Brute Force Method
Idea

Count the frequency of each element using loops.

Python Code
def majorityElement(arr):
n = len(arr)

for i in range(n):
    count = 0
    for j in range(n):
        if arr[j] == arr[i]:
            count += 1

    if count > n // 2:
        return arr[i]

return -1

print(majorityElement([1,1,2,1,3,5,1]))
Complexity
Time Space
O(n²) O(1)

Not efficient.

Approach 2: Hash Map (Dictionary Method)
Idea

Store frequency of each element using dictionary.

Python Code
def majorityElement(arr):
freq = {}
n = len(arr)

for num in arr:
    freq[num] = freq.get(num, 0) + 1

    if freq[num] > n // 2:
        return num

return -1

print(majorityElement([1,1,2,1,3,5,1]))
Complexity
Time Space
O(n) O(n)

Better method.

Approach 3: Boyer-Moore Voting Algorithm (Best Method)
Idea

This algorithm works on the concept of cancellation:

If we pair different elements, they cancel each other

The majority element will remain at the end

Steps
Take candidate and count

If count = 0 → change candidate

If same element → count++

Else → count--

Finally verify if candidate is majority

Python Code
def majorityElement(arr):
candidate = None
count = 0

# Step 1: Find candidate
for num in arr:
    if count == 0:
        candidate = num

    if num == candidate:
        count += 1
    else:
        count -= 1

# Step 2: Verify candidate
if arr.count(candidate) > len(arr) // 2:
    return candidate

return -1

print(majorityElement([1,1,2,1,3,5,1]))
Example Walkthrough
arr = [1,1,2,1,3,5,1]

Step process:
Candidate = 1
Final candidate = 1
Count occurrences = 4 > 3
Majority element = 1
Complexity Comparison
Approach Time Space
Brute Force O(n²) O(1)
Hash Map O(n) O(n)
Boyer-Moore O(n) O(1)

Best Approach → Boyer-Moore Voting Algorithm

Conclusion

To find the majority element:

Brute force is slow

Hash map is better

Boyer-Moore Voting Algorithm is the best solution

It works in:

Time = O(n)
Space = O(1)

This is a very important algorithm for interviews and exams.