Introduction

Finding the majority element in an array is a common coding problem that often appears in technical interviews. The Boyer-Moore Voting Algorithm is one of the most efficient ways to solve this problem in O(N) time and O(1) space.

This guide will cover:

• The problem statement.
• Different approaches and their pros and cons.
• A detailed explanation of the Boyer-Moore Voting Algorithm with examples.
• How to recognize when to use this algorithm.
• Edge cases to consider.

Problem Statement

Given an array nums of size n, find the majority element, which appears more thann/2 times.
You must solve this in O(N) time and O(1) space.

Example 1

Input: nums = [3,3,4,2,3,3,3]
Output: 3

Example 2

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Basic Approaches

1. Sorting Approach

• Sort the array.
• The middle element (nums[n/2]) will always be the majority element.

Code:

function majorityElement(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
}

Time Complexity: O(N log N)

Space Complexity: O(1)

Downside: Sorting takes extra time, which is unnecessary.

2. Using a Hash Map

• Use a Map to count occurrences of each number.
• Return the number that appears more than n/2 times.

Code:

function majorityElement(nums) {
    const countMap = new Map();
    const n = nums.length;
    
    for (let num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
        if (countMap.get(num) > n / 2) return num;
    }
}

Time Complexity: O(N)

Space Complexity: O(N)

Downside: Extra space is required to store counts.

Boyer-Moore Voting Algorithm (Optimal Solution)

How It Works

• The majority element appears more than n/2 times.
• If we remove pairs of different numbers, the majority element will always remain.

Algorithm Steps

1. Keep a candidate and a count.
2. Go through the array:
   • If count == 0, set the current number as the new candidate.
   • If the number is the same as the candidate, increase count.
   • Otherwise, decrease count.
3. The final candidate is the majority element.

Code Implementation

function majorityElement(nums) {
    let candidate = null;
    let count = 0;

    for (let num of nums) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }

    return candidate;
}

Time Complexity: O(N)

Space Complexity: O(1)

Example Walkthrough

Consider nums = [2, 2, 1, 1, 1, 2, 2]

Final majority element = 2

Why This Works

1. Since the majority element appears more than n/2 times, it cannot be removed completely.
2. Non-majority elements cancel each other out.
3. By the end, the majority element remains as the last candidate.

When to Use This Algorithm

The Boyer-Moore Voting Algorithm is useful when:
✔ You need to find the most frequently occurring element.
✔ The element appears more than n/2 times.
✔ You need a fast and memory-efficient solution.

Handling Edge Cases

Single Element Array

Input: [1]
Output: 1

All Elements Are the Same

Input: [7,7,7,7]
Output: 7

Already Majority at Start

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

Minimum Majority Case

Input: [1,1,2,2,2]
Output: 2

What If We Need to Find Elements Appearing More Than n/3 Times?

The Boyer-Moore algorithm can be extended to find elements appearing more than n/3 times:

1. Instead of one candidate, track two.
2. Decrease count when neither matches.
3. Verify candidates in a second pass.

Code for n/3 Majority Elements

function majorityElementN3(nums) {
    let candidate1 = null, count1 = 0;
    let candidate2 = null, count2 = 0;

    for (let num of nums) {
        if (num === candidate1) count1++;
        else if (num === candidate2) count2++;
        else if (count1 === 0) (candidate1 = num, count1 = 1);
        else if (count2 === 0) (candidate2 = num, count2 = 1);
        else (count1--, count2--);
    }

    return [candidate1, candidate2].filter(c => nums.filter(x => x === c).length > nums.length / 3);
}

Final Thoughts

• The Boyer-Moore Voting Algorithm is the most efficient way to find the majority element in O(N) time and O(1) space.
• It works by canceling out non-majority elements using a voting process.
• It can be extended to solve other problems, such as finding elements appearing more than n/3 times.

This algorithm is widely asked in technical interviews, so understanding it well will help you in coding challenges.