Majority Element

LeetCode 169 | Difficulty: Easy

Easy

Problem Description

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.

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^4`

- `-10^9 <= nums[i] <= 10^9`

- The input is generated such that a majority element will exist in the array.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Topics: Array, Hash Table, Divide and Conquer, Sorting, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 137 ms)

Metric	Value
Runtime	137 ms
Memory	41 MB
Date	2022-02-21

Solution

public class Solution {
    public int MajorityElement(int[] nums) {
        int c = 0, m = 0;
        foreach(var x in nums)
        {
            if(c==0) 
            {
                m = x;
                c=1;
            }
            else if(x==m)
                c++;
            else c--;
        }
        return m;
}
}

📜 3 more C# submission(s)

Submission (2022-02-08) — 144 ms, 40.6 MB

public class Solution {
    public int MajorityElement(int[] nums) {
        int c = 0, m = 0;
        foreach(var x in nums)
        {
            if(c==0) 
            {
                m = x;
                c=1;
            }
            else if(x==m)
                c++;
            else c--;
        }
        return m;
}
}

Submission (2017-12-28) — 166 ms, N/A

public class Solution {
    public int MajorityElement(int[] nums) {
        int count=1, majorityNum = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        if(count==0)
        {
            majorityNum = nums[i];
            count=1;
        }
        else if(nums[i]==majorityNum)
        {
            count++;
        }
        else count--;
    }
    return majorityNum;
    }
}

Submission (2017-12-28) — 222 ms, N/A

public class Solution {
    public int MajorityElement(int[] nums) {
        Dictionary<int,int> numOccurences = new Dictionary<int, int>();
    int max = 0, maxNum = 0;
    foreach (var number in nums)
    {
        if(!numOccurences.ContainsKey(number))
        {
            numOccurences.Add(number,1);
            
        }
        else
        {
            numOccurences[number]++;
        }
        if(max<numOccurences[number])
        {
            max = numOccurences[number];
            maxNum = number;
        }
    }
    return maxNum;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.