#169MediumBoyer-Moore Voting

Majority Element

Boyer-Moore Voting: the majority element survives the vote cancellation.

AmazonGoogleZenefitsMicrosoft

Problem Statement

Given an array nums of size n, return the majority element — the element that appears more than ⌊n/2⌋ times. You may assume the majority element always exists.

Examples

Example 1

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

Example 2

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

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 5 × 10⁴
  • −2³¹ ≤ nums[i] ≤ 2³¹ − 1
  • Majority element always exists.

Solutions

1
Hash Map — Count frequencies
TimeO(n)SpaceO(n)

Count each element's frequency. Return the one that appears > n/2 times. O(n) time and space.

Visual Animation
def majorityElement(nums: list[int]) -> int:
    counts = {}
    for n in nums:
        counts[n] = counts.get(n, 0) + 1
        if counts[n] > len(nums) // 2:
            return n

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine LearningBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Boyer-Moore Voting to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems