Majority Element

High school students are voting for their class president and you're tasked with counting the votes. Each presidential candidate is represented by a unique integer and the candidate that should win the election is the candidate that has received more than half the votes. Given a list of integers, return the candidate that should become the class president.

Note: You may assume there is always a candidate that has received more than half the votes.

Example(s)

Example 1:

Input: votes = [1, 1, 2, 2, 1]
Output: 1
Explanation:
- Candidate 1: 3 votes (more than half of 5 votes)
- Candidate 2: 2 votes
Candidate 1 wins.

Example 2:

Input: votes = [1, 3, 2, 3, 1, 2, 3, 3, 3]
Output: 3
Explanation:
- Candidate 3: 5 votes (more than half of 9 votes)
- Candidate 1: 2 votes
- Candidate 2: 2 votes
Candidate 3 wins.

Example 3:

Input: votes = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation:
- Candidate 2: 4 votes (more than half of 7 votes)
- Candidate 1: 3 votes
Candidate 2 wins.

Solution

There are multiple approaches:

1. Boyer-Moore Voting Algorithm: O(n) time, O(1) space (optimal)
2. Hash Map: Count frequencies, find majority
3. Sorting: Sort and return middle element (since majority is guaranteed)

JavaScript Solution

JavaScript Solution - Boyer-Moore Voting Algorithm

/**
* Find the majority element (candidate with more than half votes)
* @param {number[]} votes - Array of votes
* @return {number} - Majority candidate
*/
function majorityElement(votes) {
let candidate = null;
let count = 0;

// Boyer-Moore Voting Algorithm
// Phase 1: Find a candidate
for (const vote of votes) {
  if (count === 0) {
    candidate = vote;
    count = 1;
  } else if (vote === candidate) {
    count++;
  } else {
    count--;
  }
}

// Since problem guarantees majority exists, candidate is the answer
// In general, you might want to verify:
// let verifyCount = 0;
// for (const vote of votes) {
//   if (vote === candidate) verifyCount++;
// }
// if (verifyCount > votes.length / 2) return candidate;

return candidate;
}

// Test cases
console.log('Example 1:', majorityElement([1, 1, 2, 2, 1])); // 1
console.log('Example 2:', majorityElement([1, 3, 2, 3, 1, 2, 3, 3, 3])); // 3
console.log('Example 3:', majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2
console.log('Test 4:', majorityElement([3, 2, 3])); // 3

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Boyer-Moore Voting Algorithm

from typing import List

def majority_element(votes: List[int]) -> int:
  """
  Find the majority element (candidate with more than half votes)
  
  Args:
      votes: List of votes
      
  Returns:
      int: Majority candidate
  """
  candidate = None
  count = 0
  
  # Boyer-Moore Voting Algorithm
  # Phase 1: Find a candidate
  for vote in votes:
      if count == 0:
          candidate = vote
          count = 1
      elif vote == candidate:
          count += 1
      else:
          count -= 1
  
  # Since problem guarantees majority exists, candidate is the answer
  # In general, you might want to verify:
  # verify_count = sum(1 for v in votes if v == candidate)
  # if verify_count > len(votes) / 2:
  #     return candidate
  
  return candidate

# Test cases
print('Example 1:', majority_element([1, 1, 2, 2, 1]))  # 1
print('Example 2:', majority_element([1, 3, 2, 3, 1, 2, 3, 3, 3]))  # 3
print('Example 3:', majority_element([2, 2, 1, 1, 1, 2, 2]))  # 2
print('Test 4:', majority_element([3, 2, 3]))  # 3

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Hash Map)

Here's a hash map approach that counts frequencies:

JavaScript Hash Map

/**
 * Hash map approach
 */
function majorityElementHash(votes) {
  const frequency = new Map();
  const n = votes.length;
  
  // Count frequencies
  for (const vote of votes) {
    frequency.set(vote, (frequency.get(vote) || 0) + 1);
  }
  
  // Find candidate with more than n/2 votes
  for (const [candidate, count] of frequency.entries()) {
    if (count > n / 2) {
      return candidate;
    }
  }
  
  return -1; // Should never reach here if majority is guaranteed
}

Python Hash Map

from collections import Counter

def majority_element_hash(votes: List[int]) -> int:
    """
    Hash map approach
    """
    frequency = Counter(votes)
    n = len(votes)
    
    # Find candidate with more than n/2 votes
    for candidate, count in frequency.items():
        if count > n / 2:
            return candidate
    
    return -1  # Should never reach here if majority is guaranteed

Alternative Solution (Sorting)

Since majority is guaranteed, we can sort and return the middle element:

JavaScript Sorting

/**
 * Sorting approach
 * Since majority is guaranteed, middle element is always the majority
 */
function majorityElementSort(votes) {
  votes.sort((a, b) => a - b);
  return votes[Math.floor(votes.length / 2)];
}

Python Sorting

def majority_element_sort(votes: List[int]) -> int:
    """
    Sorting approach
    Since majority is guaranteed, middle element is always the majority
    """
    votes.sort()
    return votes[len(votes) // 2]

Complexity

• Time Complexity:
  • Boyer-Moore: O(n) - Single pass through the array
  • Hash Map: O(n) - Count frequencies, then find majority
  • Sorting: O(n log n) - Sorting takes O(n log n)
• Space Complexity:
  • Boyer-Moore: O(1) - Only uses two variables
  • Hash Map: O(n) - Store frequency of each unique candidate
  • Sorting: O(1) or O(n) depending on sorting algorithm (in-place vs not)

Approach

The Boyer-Moore Voting Algorithm is optimal:

1. Initialize: candidate = null, count = 0
2. Traverse array: For each vote:
   • If count === 0: Set current vote as candidate, set count = 1
   • Else if vote === candidate: Increment count
   • Else: Decrement count
3. Result: The candidate at the end is the majority element

Why it works:

• The majority element appears more than n/2 times
• All other elements combined appear less than n/2 times
• When we cancel out votes, the majority element will always "win"

Key Insights

• Boyer-Moore algorithm: Elegant O(n) time, O(1) space solution
• Majority guaranteed: Problem states majority always exists
• More than half: Majority means > n/2, not just ≥ n/2
• Vote cancellation: Algorithm cancels out non-majority votes
• Single pass: Only need one traversal

Step-by-Step Example

Let's trace through Example 1: votes = [1, 1, 2, 2, 1]

Initial: candidate = null, count = 0

Vote 1 (value 1):
  count === 0? Yes
  candidate = 1, count = 1

Vote 2 (value 1):
  vote === candidate? Yes (1 === 1)
  count = 2

Vote 3 (value 2):
  vote === candidate? No (2 !== 1)
  count = 1

Vote 4 (value 2):
  vote === candidate? No (2 !== 1)
  count = 0

Vote 5 (value 1):
  count === 0? Yes
  candidate = 1, count = 1

Final: candidate = 1

Let's trace through Example 2: votes = [1, 3, 2, 3, 1, 2, 3, 3, 3]

Vote 1 (1): candidate=1, count=1
Vote 2 (3): candidate=1, count=0 (cancel)
Vote 3 (2): candidate=2, count=1 (new candidate)
Vote 4 (3): candidate=2, count=0 (cancel)
Vote 5 (1): candidate=1, count=1 (new candidate)
Vote 6 (2): candidate=1, count=0 (cancel)
Vote 7 (3): candidate=3, count=1 (new candidate)
Vote 8 (3): candidate=3, count=2
Vote 9 (3): candidate=3, count=3

Final: candidate = 3

Visual Representation

Example 1: votes = [1, 1, 2, 2, 1]

Vote cancellation:
1 1 2 2 1
↑ ↑     ↑
Majority: 1 (3 votes out of 5)

Boyer-Moore process:
1: candidate=1, count=1
1: candidate=1, count=2
2: candidate=1, count=1 (cancel one)
2: candidate=1, count=0 (cancel one)
1: candidate=1, count=1 (new candidate)

Result: 1

Edge Cases

• All same votes: Works correctly (majority is that value)
• Two candidates: One must have majority (guaranteed by problem)
• Single vote: That vote is the majority
• Large array: Boyer-Moore handles efficiently

Important Notes

• Majority guaranteed: Problem states majority always exists
• More than half: Majority means strictly > n/2, not ≥ n/2
• Boyer-Moore: Most efficient (O(n) time, O(1) space)
• Verification: In general, you might want to verify the result (but problem guarantees it)

Comparison of Approaches

Approach	Time	Space	Notes
Boyer-Moore	O(n)	O(1)	Optimal, elegant
Hash Map	O(n)	O(n)	Simple, intuitive
Sorting	O(n log n)	O(1)	Simple but slower

Related Problems

• Majority Element II: Find all elements appearing more than n/3 times
• Find the Duplicate Number: Different problem but similar techniques
• Top K Frequent Elements: Find k most frequent elements
• Count Primes: Different counting problem

Takeaways

• Boyer-Moore algorithm is optimal for majority element
• O(1) space is achievable with Boyer-Moore
• Vote cancellation is the key insight
• Majority guaranteed simplifies the problem
• Single pass is sufficient with Boyer-Moore