Introduction
Finding the most frequent element in an array might seem simple, but doing it efficiently is the real challenge.
This problem introduces a powerful technique called the Boyer-Moore Voting Algorithm, which solves it in linear time and constant space.
Problem Statement
Given an array arr, find the majority element.
A majority element is one that appears more than n/2 times.
- If it exists → return the element
- If not → return
-1
Example 1
Input:
```python id="z1mqz9"
arr = [1, 1, 2, 1, 3, 5, 1]
Output:
```python id="sdif4r"
1
Example 2
Input:
```python id="q3m2zx"
arr = [7]
Output:
```python id="d9q2k3"
7
Example 3
Input:
```python id="v2g9bn"
arr = [2, 13]
Output:
```python id="l0w7fp"
-1
Brute Force Approach
- Count frequency of each element
- Return element with count > n/2
Time Complexity: O(n²)
Better Approach (Hash Map)
- Use a dictionary to count frequencies
Time Complexity: O(n)
Space Complexity: O(n)
Optimal Approach: Boyer-Moore Voting Algorithm
Key Idea
Maintain:
candidatecount
If count becomes 0 → pick new candidate
Increase count if same element
Decrease count if different
Why It Works
The majority element appears more than half the time, so it cannot be canceled out by other elements.
Python Implementation
```python id="kl8r8o"
def majority_element(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
Example usage
arr = [1, 1, 2, 1, 3, 5, 1]
print(majority_element(arr))
---
## Step-by-Step Example
For:
```python id="wz0l9h"
[1, 1, 2, 1, 3, 5, 1]
- Start with candidate = 1
- Matching values increase count
- Different values decrease count
- Final candidate remains 1
Key Points
- No extra space required
- Works in a single pass
- Must verify candidate at the end
- Very important interview algorithm
Conclusion
The Majority Element problem demonstrates how smart observation can lead to highly efficient algorithms. The Boyer-Moore Voting Algorithm is a must-know technique for coding interviews and competitive programming.
Understanding this approach helps you solve many similar problems involving frequency and dominance in arrays.