Find the Majority Element

Problem Statement

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

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

If no such element exists, return -1.

Example 1

Input:

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

Output:

1

Explanation:
Array size = 7
n/2 = 3.5
Element 1 appears 4 times → 4 > 3.5 → Majority element

Example 2

Input:

arr = [7]

Output:

7

Explanation:
Array size = 1
7 appears once → 1 > 0.5 → Majority element

Example 3

Input:

arr = [2, 13]

Output:

-1

Explanation:
Array size = 2
n/2 = 1
No element appears more than 1 time

Efficient Approach – Moore’s Voting Algorithm

Instead of counting frequencies using a dictionary (O(n) space),
we use Moore’s Voting Algorithm which works in:

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

Why Moore’s Voting Works

If a majority element exists:

It will survive pairwise cancellation.
Other elements cancel each other out.
The majority element remains as candidate.

The algorithm works in two phases:

Find a candidate
Verify the candidate
Step 1 – Find Candidate

We maintain:

candidate
count

Traverse the array:

If count == 0 → choose new candidate
If element == candidate → increase count
Else → decrease count
Step 2 – Verify Candidate

Count how many times the candidate appears.
If it appears more than n/2 times → return it.
Otherwise → return -1.

Python Code (Optimized O(n) Solution)
class Solution:
def majorityElement(self, arr):
count = 0
candidate = None

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

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

    return -1

Dry Run Example

Input:

[1, 1, 2, 1, 3, 5, 1]

Iteration process:

candidate = 1, count = 1
candidate = 1, count = 2
count decreases (2 encountered)
candidate = 1, count = 2
count decreases (3 encountered)
count decreases (5 encountered)
candidate = 1, count = 1

Final candidate = 1
Verify → appears 4 times
4 > 7//2 → return 1

Why This Is Optimal

Brute Force → O(n²)
Using dictionary → O(n) time + O(n) space
Moore’s Voting → O(n) time + O(1) space