Majority Element (Boyer - Moore Voting Algorithm)

Python Java C++

def majorityElement(nums):
    # Initialize count and first element as potential majority
    count = 0
    curr = nums[0]
    
    # Apply Boyer-Moore voting
    for num in nums:
        if num == curr: count += 1
        else: count -= 1
        
        if count < 0:
            curr = num
            count = 1
            
    return curr

class Solution {
    // Boyer moore voting algorithm
    public int majorityElement(int[] nums) {
        // Count tracks current element frequency, curr is potential majority element
        int count = 0;
        int curr = nums[0];

        for (int num : nums) {
            // Increment count if same element, decrement if different
            if (num == curr) count++; else count--;
            
            // If count becomes negative, switch to new potential majority
            if (count < 0) {
                curr = num;
                count = 1;
            }
        }

        return curr;
    }
}

class Solution {
public:
    int majorityElement(vector& nums) {
        // Initialize count and first element as potential majority
        int count = 0;
        int curr = nums[0];
        
        // Apply Boyer-Moore voting
        for (int num : nums) {
            if (num == curr) count++; else count--;
            
            if (count < 0) {
                curr = num;
                count = 1;
            }
        }
        
        return curr;
    }
};

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.

Category: Array Algorithm | Difficulty: Easy

Detailed Explanation

Approach

This solution uses the Boyer-Moore Voting Algorithm, which is optimal for finding a majority element. The algorithm works by maintaining a count and a candidate for majority element, using a clever cancellation strategy.

Key Concepts

1. Count Variable: Keeps track of the current element's "votes"
2. Current Element: The current candidate for majority element
3. Voting Process: Elements equal to candidate add a vote, different elements remove a vote

Algorithm Steps

1. Initialize first element as the candidate
2. For each element:
   • If it matches candidate, increment count
   • If different, decrement count
   • If count becomes negative, switch candidate and reset count to 1

Time and Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only using two variables

Why It Works

The algorithm works because the majority element appears more than n/2 times, meaning it will always have more "votes" than the sum of all other elements' votes. Even if we switch candidates multiple times, the majority element will eventually become and remain the candidate.

Visual Example

nums = [2,2,1,1,1,2,2]
Step by step:
2 -> count = 1, curr = 2
2 -> count = 2, curr = 2
1 -> count = 1, curr = 2
1 -> count = 0, curr = 2
1 -> count = -1, curr = 1 (switch)
2 -> count = 0, curr = 1
2 -> count = -1, curr = 2 (switch)

Result: 2

Edge Cases

• Array of length 1: First element is majority
• All elements same: First element is majority
• No need to validate majority as it's guaranteed to exist