CA 21 - Majority Element

Problem Statement

Given an array arr[]. Find the majority element in the array. If no majority element exists, return -1.

Note: A majority element is an element that appears strictly more than arr.size()/2 times in the array.

Examples:

Input: arr[] = [1, 1, 2, 1, 3, 5, 1]
Output: 1
Explanation: Since 1 appears more than 7/2 times, it is the majority element.

Input: arr[] = [7]
Output: 7

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

My Goal

For this problem, my goal was to:

Identify elements with high frequency efficiently
Avoid using extra space like hash maps
Solve the problem in optimal time
Learn an important algorithmic pattern

Solution

I used Moore’s Voting Algorithm, which is the most optimal solution for this problem.

Idea:

Maintain a candidate and a count
If count becomes 0 → choose new candidate
Increase count if same element
Decrease count if different element

At the end, verify if the candidate is actually a majority.

Solution Code (Python)

a = [1, 1, 2, 1, 3, 5, 1]

c = None
cnt = 0

for x in a:
    if cnt == 0:
        c = x
    if x == c:
        cnt += 1
    else:
        cnt -= 1

# verify candidate
if a.count(c) > len(a) // 2:
    print(c)
else:
    print(-1)

Explanation

First pass finds a potential candidate
Second step verifies if it appears more than n/2 times
If yes → majority element
Else → return -1