Find the Majority Element

Introduction

In many problems, we need to identify the most frequent element in an array.

The majority element is the one that appears more than n/2 times.

This problem can be solved efficiently using the Boyer-Moore Voting Algorithm, which is optimal.

Problem Statement

Given an array arr[], find the majority element.

Conditions:

• Majority element appears more than n/2 times
• If no such element exists → return -1

Examples

Example 1:
Input: [1, 1, 2, 1, 3, 5, 1]
Output: 1

Example 2:
Input: [7]
Output: 7

Example 3:
Input: [2, 13]
Output: -1

Intuition

• Majority element dominates all others combined
• We cancel out different elements

Approach

Algorithm Steps

• Initialize:

  • candidate = None
  • count = 0

• Traverse array:

  • If count == 0 → set new candidate
  • If element == candidate → increment count
  • Else → decrement count

• Verify candidate:

  • Count its frequency
  • If > n/2 → return candidate
  • Else → return -1

Code (Python)

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

Step-by-Step Explanation

For [1, 1, 2, 1, 3, 5, 1]:

• Start → candidate = 1
• Match → increase count
• Different → decrease count
• Majority survives cancellation

Final → candidate = 1

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Conclusion

The algorithm is an elegant solution for finding the majority element efficiently.