Find Majority Element (Boyer-Moore Algorithm)

Find the majority element that appears more than n/2 times using Boyer-Moore majority vote algorithm

Language Selection

Choose your preferred programming language

Showing: Python

Find Majority Element (Boyer-Moore Algorithm)

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Constraints:

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

Examples:

Example 1:

Input: nums = [3,2,3]
Output: 3
Explanation: 3 appears 2 times, which is more than ⌊3/2⌋ = 1.

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation: 2 appears 4 times, which is more than ⌊7/2⌋ = 3.

Example 3:

Input: nums = [1]
Output: 1
Explanation: The single element is the majority.

Approach 1: Boyer-Moore Majority Vote Algorithm (Optimal)

Algorithm:

Initialize candidate and count
For each element, if count is 0, set current element as candidate
If current element equals candidate, increment count; otherwise decrement
The candidate at the end is the majority element

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

Python:

def majorityElement(nums):
    """
    Find majority element using Boyer-Moore algorithm
    Time: O(n)
    Space: O(1)
    """
    candidate = None
    count = 0
    
    # Phase 1: Find candidate
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    
    return candidate

Java:

class Solution {
    /**
     * Find majority element using Boyer-Moore algorithm
     * Time: O(n)
     * Space: O(1)
     */
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        // Phase 1: Find candidate
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
}

Go:

// majorityElement - Find majority element using Boyer-Moore algorithm
// Time: O(n)
// Space: O(1)
func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    
    // Phase 1: Find candidate
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    
    return candidate
}

JavaScript:

/**
 * Find majority element using Boyer-Moore algorithm
 * Time: O(n)
 * Space: O(1)
 */
function majorityElement(nums) {
    let candidate = null;
    let count = 0;
    
    // Phase 1: Find candidate
    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }
    
    return candidate;
}

C#:

public class Solution {
    /// <summary>
    /// Find majority element using Boyer-Moore algorithm
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MajorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        // Phase 1: Find candidate
        foreach (int num in nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
}

Approach 2: Hash Map

Algorithm:

Count frequency of each element using a hash map
Return the element with frequency greater than n/2

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

Python:

def majorityElement(nums):
    """
    Find majority element using hash map
    Time: O(n)
    Space: O(n)
    """
    count = {}
    n = len(nums)
    
    for num in nums:
        count[num] = count.get(num, 0) + 1
        if count[num] > n // 2:
            return num
    
    return None

Java:

class Solution {
    /**
     * Find majority element using hash map
     * Time: O(n)
     * Space: O(n)
     */
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int n = nums.length;
        
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
            if (count.get(num) > n / 2) {
                return num;
            }
        }
        
        return -1; // Should never reach here
    }
}

Go:

// majorityElement - Find majority element using hash map
// Time: O(n)
// Space: O(n)
func majorityElement(nums []int) int {
    count := make(map[int]int)
    n := len(nums)
    
    for _, num := range nums {
        count[num]++
        if count[num] > n/2 {
            return num
        }
    }
    
    return -1 // Should never reach here
}

JavaScript:

/**
 * Find majority element using hash map
 * Time: O(n)
 * Space: O(n)
 */
function majorityElement(nums) {
    const count = new Map();
    const n = nums.length;
    
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
        if (count.get(num) > n / 2) {
            return num;
        }
    }
    
    return null; // Should never reach here
}

C#:

public class Solution {
    /// <summary>
    /// Find majority element using hash map
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int MajorityElement(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int n = nums.Length;
        
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            
            if (count[num] > n / 2) {
                return num;
            }
        }
        
        return -1; // Should never reach here
    }
}

Approach 3: Sorting

Algorithm:

Sort the array
The majority element will be at index n/2

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

Python:

def majorityElement(nums):
    """
    Find majority element using sorting
    Time: O(n log n)
    Space: O(1)
    """
    nums.sort()
    return nums[len(nums) // 2]

Java:

class Solution {
    /**
     * Find majority element using sorting
     * Time: O(n log n)
     * Space: O(1)
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

Go:

// majorityElement - Find majority element using sorting
// Time: O(n log n)
// Space: O(1)
func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

JavaScript:

/**
 * Find majority element using sorting
 * Time: O(n log n)
 * Space: O(1)
 */
function majorityElement(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
}

C#:

public class Solution {
    /// <summary>
    /// Find majority element using sorting
    /// Time: O(n log n)
    /// Space: O(1)
    /// </summary>
    public int MajorityElement(int[] nums) {
        Array.Sort(nums);
        return nums[nums.Length / 2];
    }
}

Approach 4: Randomization

Algorithm:

Randomly pick an element
Count its frequency
If it’s majority, return it; otherwise repeat

Time Complexity: O(n) average case
Space Complexity: O(1)

Python:

import random

def majorityElement(nums):
    """
    Find majority element using randomization
    Time: O(n) average case
    Space: O(1)
    """
    while True:
        candidate = random.choice(nums)
        count = sum(1 for num in nums if num == candidate)
        if count > len(nums) // 2:
            return candidate

Java:

import java.util.Random;

class Solution {
    /**
     * Find majority element using randomization
     * Time: O(n) average case
     * Space: O(1)
     */
    public int majorityElement(int[] nums) {
        Random rand = new Random();
        
        while (true) {
            int candidate = nums[rand.nextInt(nums.length)];
            int count = 0;
            
            for (int num : nums) {
                if (num == candidate) {
                    count++;
                }
            }
            
            if (count > nums.length / 2) {
                return candidate;
            }
        }
    }
}

Go:

import "math/rand"
import "time"

// majorityElement - Find majority element using randomization
// Time: O(n) average case
// Space: O(1)
func majorityElement(nums []int) int {
    rand.Seed(time.Now().UnixNano())
    
    for {
        candidate := nums[rand.Intn(len(nums))]
        count := 0
        
        for _, num := range nums {
            if num == candidate {
                count++
            }
        }
        
        if count > len(nums)/2 {
            return candidate
        }
    }
}

JavaScript:

/**
 * Find majority element using randomization
 * Time: O(n) average case
 * Space: O(1)
 */
function majorityElement(nums) {
    while (true) {
        const candidate = nums[Math.floor(Math.random() * nums.length)];
        let count = 0;
        
        for (const num of nums) {
            if (num === candidate) {
                count++;
            }
        }
        
        if (count > nums.length / 2) {
            return candidate;
        }
    }
}

C#:

using System;

public class Solution {
    private static Random rand = new Random();
    
    /// <summary>
    /// Find majority element using randomization
    /// Time: O(n) average case
    /// Space: O(1)
    /// </summary>
    public int MajorityElement(int[] nums) {
        while (true) {
            int candidate = nums[rand.Next(nums.Length)];
            int count = 0;
            
            foreach (int num in nums) {
                if (num == candidate) {
                    count++;
                }
            }
            
            if (count > nums.Length / 2) {
                return candidate;
            }
        }
    }
}

Key Insights

Boyer-Moore Algorithm: The most elegant solution that uses the fact that majority element appears more than n/2 times.
Voting Concept: Each non-majority element can “cancel out” at most one majority element, but majority elements will still remain.
Mathematical Proof: If majority element exists, it will survive the voting process.
Space Efficiency: Boyer-Moore uses only O(1) space, making it optimal.

Edge Cases

Single element: [1] → result is 1
Two elements: [1,2,1] → result is 1
All same elements: [2,2,2,2] → result is 2
Majority at beginning: [3,3,1,2] → result is 3
Majority at end: [1,2,3,3] → result is 3

Test Cases

# Test case 1: Normal case
assert majorityElement([3,2,3]) == 3

# Test case 2: Multiple elements
assert majorityElement([2,2,1,1,1,2,2]) == 2

# Test case 3: Single element
assert majorityElement([1]) == 1

# Test case 4: All same elements
assert majorityElement([5,5,5,5]) == 5

# Test case 5: Majority at different positions
assert majorityElement([1,2,2,2,3]) == 2

Follow-up Questions

Majority Element II: Find all elements that appear more than n/3 times.
Majority Element with Verification: What if we’re not guaranteed that majority element exists?
Streaming Majority Element: Find majority element in a stream of data.
Distributed Majority Element: Find majority element across multiple machines.

Common Mistakes

Not understanding Boyer-Moore: The algorithm is counter-intuitive and requires understanding of the voting concept.
Incorrect count logic: Not properly handling the increment/decrement of count.
Assuming sorted array: The sorting approach works but is less efficient.
Not handling edge cases: Forgetting to handle single element arrays.

Trade-offs

Boyer-Moore vs Hash Map: Boyer-Moore is more space-efficient, hash map is easier to understand
Sorting: Simple but less efficient due to O(n log n) time complexity
Randomization: Probabilistic approach, not deterministic
Space vs Time: Boyer-Moore provides optimal space complexity