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 then return the element
• If not then return -1

Example 1

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

Output:
1

Example 2

Input:

arr = [7]

Output:

7

Example 3

Input:

arr = [2, 13]

Output:

-1

Brute Force Approach

• Count frequency of each element
• Return element with count > n/2

Time Complexity: O(n^2)

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 then 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

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:

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