Majority Element

Like0

Ever been in a situation where one voice clearly drowns out the rest? That’s exactly what the Majority Element is! You’re given an array of numbers, and your mission is to find the one that appears more than half the time (more than n/2). You can always assume that such a "leader" exists in the crowd.

The "secret sauce" here is a Frequency Map. While there are exotic ways to solve this (like Boyer-Moore Voting), the most intuitive way is to keep a tally of each number as you scan. Think of it like an election: every time you see a number, you give it a vote in your Map. As soon as a number’s vote count crosses the "more than half" threshold, you declare it the winner! This approach gives you a linear O(n) efficiency, making it perfect for large datasets. It’s a fundamental pattern for identifying dominance in any collection of data before moving to more complex stats!

Examples

Example 1

Input

nums = [3,2,3]

Output

Explanation

3 appears 2 times, more than n/2.

Example 2

Input

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

Output

Explanation

2 appears 4 times out of 7.

Example 3

Input

nums = [1]

Output

Explanation

Only element is majority.

Algorithm Flow

Recommendation Algorithm Flow for Majority Element - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int majority_element(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        int limit = nums.length / 2;
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
            if (freq.get(x) > limit) return x;
        }
        return nums.length > 0 ? nums[0] : 0;
    }
}

javascript

function majority_element(nums) {
    const freq = {};
    const limit = Math.floor(nums.length / 2);
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        freq[x] = (freq[x] || 0) + 1;
        if (freq[x] > limit) return x;
    }
    return nums.length ? nums[0] : 0;
}

php

<?php
function majority_element($nums) {
    $freq = [];
    $limit = intdiv(count($nums), 2);
    foreach ($nums as $x) {
        $k = (string)$x;
        $freq[$k] = ($freq[$k] ?? 0) + 1;
        if ($freq[$k] > $limit) return $x;
    }
    return count($nums) ? $nums[0] : 0;
}
?>

python

from typing import List

def majority_element(nums: List[int]) -> int:
    freq = {}
    limit = len(nums) // 2
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
        if freq[x] > limit:
            return x
    return nums[0] if nums else 0

rust

use std::collections::HashMap;
fn majority_element(nums: Vec<i32>) -> i32 {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let limit = (nums.len() / 2) as i32;
    for x in nums.iter() {
        let c = freq.entry(*x).or_insert(0);
        *c += 1;
        if *c > limit {
            return *x;
        }
    }
    if nums.is_empty() { 0 } else { nums[0] }
}

typescript

function majority_element(nums: number[]): number {
    var freq: { [key: string]: number } = {};
    var limit = Math.floor(nums.length / 2);
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        var key = String(x);
        freq[key] = (freq[key] || 0) + 1;
        if (freq[key] > limit) return x;
    }
    return nums.length ? nums[0] : 0;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Majority Element

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion