LeetCode #169 - Majority Element

📝 Introduction

Given an array nums of size n, return the majority element — the element that appears more than ⌊n / 2⌋ times.

*Constraints typically include:

• It is guaranteed that the majority element always exists in the array.*

💡 Approach & Key Insights

*The problem centers on identifying an element that occurs more than n/2 times. Three approaches are commonly used:

• Brute-force with nested loops.
• Better approach using hash map frequency counting.
• Optimal approach using Moore’s Voting Algorithm for O(n) time and O(1) space.*

🛠️ Breakdown of Approaches

1️⃣ Brute Force / Naive Approach

• Explanation: For each element, count its frequency using a nested loop. If any element occurs more than ⌊n/2⌋ times, return it.
• Time Complexity: O(n²) – due to nested iterations.
• Space Complexity: O(1)
• Example/Dry Run:

1
Input: [3, 2, 3]
2
Step 1: Check 3 → appears 2 times → not > 1.5
3
Step 2: Check 2 → appears 1 time → not > 1.5
4
Return 3

2️⃣ Better Approach

• Explanation: Use a hash map to store frequencies of each number. As you update counts, if any value exceeds ⌊n/2⌋, return it.
• Time Complexity: O(n) – single pass to count.
• Space Complexity: O(n) – for storing frequencies.
• Example/Dry Run:

1
Input: [2, 2, 1, 1, 1, 2, 2]
2
Count Map:
3
{2: 1}
4
{2: 2}
5
{2: 2, 1: 1}
6
...
7
{2: 4, 1: 3}
8
Check: 4 > floor(7/2) = 3 → return 2

3️⃣ Optimal Approach

• Explanation: Use Moore’s Voting Algorithm. Keep a count and a candidate. If count is zero, pick a new candidate. If current number equals candidate, increment count. Else decrement. At the end, the candidate is the majority element.
• Time Complexity: O(n) – single pass.
• Space Complexity: O(1) – constant space.
• Example/Dry Run:

1
Input: [2, 2, 1, 1, 1, 2, 2]
2
Step-by-step:
3
candidate = 2, count = 1
4
2 == 2 → count = 2
5
1 != 2 → count = 1
6
1 != 2 → count = 0 → candidate = 1, count = 1
7
1 == 1 → count = 2
8
2 != 1 → count = 1
9
2 != 1 → count = 0 → candidate = 2, count = 1
10
Final candidate = 2 → return 2

📊 Complexity Analysis

📉 Optimization Ideas

The Moore’s Voting Algorithm is already optimal, with a single pass and constant space. If the array does not guarantee a majority element, a second pass is needed to verify the candidate.

📌 Example Walkthroughs & Dry Runs

1
Example: [3, 3, 4, 2, 4, 4, 2, 4, 4]
2
Step-by-step:
3
candidate = 3, count = 1
4
3 == 3 → count = 2
5
4 != 3 → count = 1
6
2 != 3 → count = 0 → candidate = 2
7
...
8
Final candidate = 4 → verify by count = 5
9
n = 9 → ⌊9/2⌋ = 4 → 5 > 4 → return 4

🔗 Additional Resources

• Moore’s Voting Algorithm - GeeksforGeeks

Author: Neha Amin

Date: 19/07/2025