MAJORITY ELEMENT

How I Understood the Majority Element Problem (LeetCode / General)
When I first saw this problem, it looked tricky because it asks to find an element that appears more than half the time in an array.
After researching, I realized that the Boyer-Moore Voting Algorithm provides a linear-time, constant-space solution.

Problem
Given an array arr, find the majority element — the element that appears more than n/2 times.
If no such element exists, return -1.
Example:
Python
arr = [3, 3, 4, 2, 3, 3, 3]

Output: 3

Python
arr = [1, 2, 3, 4]

Output: -1

What I Noticed
A naive solution is to count each element, but that requires extra space or multiple passes.
Instead, Boyer-Moore Voting Algorithm cleverly uses:
A candidate element
A count to track potential majority
By pairing off different elements, the majority element (if it exists) survives at the end.

** What Helped Me**
The algorithm has two phases:
Finding a candidate
Initialize candidate = None and count = 0
For each element x:
If count == 0, set candidate = x and count = 1
If x == candidate, increment count
Else, decrement count
Verifying the candidate
Count how many times candidate appears
If it appears more than n//2 → return it
Else → return -1
This guarantees correct results in O(n) time and O(1) space.

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

    # Phase 1: Finding the candidate
    for x in arr:
        if count == 0:
            candidate = x
            count = 1
        elif x == candidate:
            count += 1
        else:
            count -= 1

    # Phase 2: Verifying the candidate
    actual_count = 0
    for x in arr:
        if x == candidate:
            actual_count += 1

    if actual_count > n // 2:
        return candidate
    else:
        return -1

Example Usage
Python
arr = [3, 3, 4, 2, 3, 3, 3]
solution = Solution()
print(solution.majorityElement(arr))
Output:
Plain text
3

Complexity
Time: O(n) — iterate through the array twice
Space: O(1) — only a few variables

What I Learned
This problem demonstrates that:
You don’t always need hash maps or sorting
Clever use of counters can reduce space and simplify logic
Pairing off elements helps identify the majority efficiently

Final Thought
At first, I thought this problem might require complex data structures.
Once I realized:
“Keep a candidate and a count, then verify”
…it became simple, elegant, and highly efficient.
Boyer-Moore is a classic example of clever linear-time algorithms.