Majority Element

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:

  • candidate
  • count

• 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.