Skip to main content
CodePeetCodePeet
CodePeet 250

Majority Element

EASYProblemSolveExternal Links

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.

In other words, one element is guaranteed to occur more frequently than all other elements combined. Your task is to identify and return that element.

Examples

Example 1

Input: nums = [3, 2, 3]

Output: 3

Explanation: The array has 3 elements, so the majority element must appear more than ⌊3/2⌋ = 1 time — i.e., at least 2 times. The element 3 appears twice (indices 0 and 2), while 2 appears once. Since 3 appears more than half the time, it is the majority element.

Example 2

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

Output: 2

Explanation: The array has 7 elements, so the majority element must appear more than ⌊7/2⌋ = 3 times — i.e., at least 4 times. The element 2 appears 4 times (indices 0, 1, 5, 6), and 1 appears 3 times. Since 2 appears more than half the time, it is the majority element.

Example 3

Input: nums = [1]

Output: 1

Explanation: With only one element, that element trivially appears more than ⌊1/2⌋ = 0 times. So 1 is the majority element.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 5 × 10^4
  • -10^9 ≤ nums[i] ≤ 10^9
  • The majority element is guaranteed to exist in the array.

Editorial

Brute Force

Intuition

The most direct way to find the majority element is to check, for each distinct element in the array, how many times it appears. If its count exceeds ⌊n/2⌋, we have found the majority element.

Imagine you are in a crowded room and you want to figure out which colour of shirt is worn by more than half the people. The simplest strategy: pick a person, count how many others are wearing the same colour. If it is more than half, you are done. If not, pick a different person and repeat.

This approach checks every element against every other element, leading to nested loops and quadratic work.

Step-by-Step Explanation

Let's trace through with nums = [2, 2, 1, 1, 1, 2, 2]:

Step 1: Pick the first element nums[0] = 2. Count how many times 2 appears in the entire array.

  • Scan: 2, 2, 1, 1, 1, 2, 2 → count = 4.
  • Is 4 > ⌊7/2⌋ = 3? YES. We found the majority element.

Step 2: Return 2.

In this case we got lucky — the majority element was the first element. But in the worst case, we might have to check every element. For example, if nums = [1, 1, 1, 2, 2, 2, 2], we would first count 1s (3 ≤ 3, not majority), then count 2s (4 > 3, majority found).

Brute Force — Count Each Element's Occurrences — Watch how we pick each candidate element and scan the entire array to count its occurrences, stopping as soon as we find one that exceeds the majority threshold.

Algorithm

  1. For each element nums[i] in the array:
    a. Initialize a counter to 0.
    b. For each element nums[j] in the array:
    • If nums[j] == nums[i], increment the counter.
      c. If counter > ⌊n/2⌋, return nums[i].
  2. Return -1 (unreachable given problem guarantees).

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count > n / 2) {
                return nums[i];
            }
        }
        return -1; // Should never reach here
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        n = len(nums)
        for i in range(n):
            count = 0
            for j in range(n):
                if nums[j] == nums[i]:
                    count += 1
            if count > n // 2:
                return nums[i]
        return -1  # Should never reach here
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count > n / 2) {
                return nums[i];
            }
        }
        return -1; // Should never reach here
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, we scan the entire array of n elements to count its occurrences. This gives n × n = O(n²) comparisons in the worst case.

Space Complexity: O(1)

We use only a few integer variables (i, j, count). No additional data structures are allocated.

Why This Approach Is Not Efficient

The brute force runs in O(n²) time. With n up to 5 × 10^4, this means up to 2.5 × 10^9 operations — far too slow for typical time limits of 1-2 seconds.

The core waste is redundant counting: we count the occurrences of the same value multiple times. If element 2 appears at indices 0, 1, 5, and 6, we perform a full n-element scan at each of those indices, counting 2's frequency four separate times.

Key insight: if we could remember how many times we have seen each element (rather than re-counting from scratch), we would reduce the work dramatically. A hash map lets us count every element's frequency in a single pass through the array, reducing the time from O(n²) to O(n).

Better Approach - Hash Map Counting

Intuition

Instead of repeatedly scanning for each element's count, we can walk through the array once and keep a tally in a hash map: each key is an element value, and each value is how many times that element has appeared so far.

Think of it like a vote-counting official at an election. Instead of re-reading all the ballots every time someone asks "how many votes did candidate X get?", the official reads each ballot exactly once and makes a tally mark next to the candidate's name. After reading all ballots, a quick glance at the tally sheet reveals the winner.

As soon as any element's count exceeds ⌊n/2⌋, we can return it immediately — we do not even need to finish scanning the rest of the array.

Step-by-Step Explanation

Let's trace through with nums = [2, 2, 1, 1, 1, 2, 2], threshold = ⌊7/2⌋ = 3:

Step 1: Initialize empty hash map.

Step 2: Process nums[0] = 2. Map: {2: 1}. Count of 2 is 1. Is 1 > 3? No.

Step 3: Process nums[1] = 2. Map: {2: 2}. Count of 2 is 2. Is 2 > 3? No.

Step 4: Process nums[2] = 1. Map: {2: 2, 1: 1}. Count of 1 is 1. Is 1 > 3? No.

Step 5: Process nums[3] = 1. Map: {2: 2, 1: 2}. Count of 1 is 2. Is 2 > 3? No.

Step 6: Process nums[4] = 1. Map: {2: 2, 1: 3}. Count of 1 is 3. Is 3 > 3? No.

Step 7: Process nums[5] = 2. Map: {2: 3, 1: 3}. Count of 2 is 3. Is 3 > 3? No.

Step 8: Process nums[6] = 2. Map: {2: 4, 1: 3}. Count of 2 is 4. Is 4 > 3? YES!

Step 9: Return 2.

Hash Map — Counting Element Frequencies in One Pass — Watch how we build a frequency map while scanning the array, checking after each insertion whether the current element has exceeded the majority threshold.

Algorithm

  1. Create an empty hash map (element → count).
  2. For each element nums[i]:
    a. Increment its count in the hash map.
    b. If the count exceeds ⌊n/2⌋, return nums[i].
  3. Return -1 (unreachable given problem guarantees).

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> freq;
        int threshold = nums.size() / 2;
        for (int num : nums) {
            freq[num]++;
            if (freq[num] > threshold) {
                return num;
            }
        }
        return -1; // Should never reach here
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        freq = {}
        threshold = len(nums) // 2
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
            if freq[num] > threshold:
                return num
        return -1  # Should never reach here
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        int threshold = nums.length / 2;
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
            if (freq.get(num) > threshold) {
                return num;
            }
        }
        return -1; // Should never reach here
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array once. Each hash map insertion and lookup is O(1) on average. The threshold check is also O(1). Total: n iterations × O(1) = O(n).

Space Complexity: O(n)

In the worst case, the hash map stores entries for every distinct element. If all elements are distinct (except for the majority), the map can hold up to ⌊n/2⌋ + 1 entries, which is O(n).

Why This Approach Is Not Efficient

The hash map approach is already O(n) in time, which is optimal — we must read every element at least once. However, it uses O(n) extra space for the frequency map.

The problem's follow-up challenge asks: can you solve it in O(n) time and O(1) space? The hash map cannot achieve this because it fundamentally needs memory proportional to the number of distinct elements.

Key insight: the majority element has a special property — it appears more than all other elements combined. This means if we "cancel out" each occurrence of the majority element with an occurrence of a different element, the majority element will still have leftover copies. The Boyer-Moore Voting Algorithm exploits this cancellation property to find the answer with just two variables — no map needed.

Optimal Approach - Boyer-Moore Voting Algorithm

Intuition

Imagine a room full of people, each supporting a candidate. They start pairing up with supporters of different candidates. Each pair cancels out — both people sit down. Since the majority candidate has more than half the supporters, after all possible cancellations, some supporters of the majority candidate will remain standing. The last group standing is the majority.

The Boyer-Moore Voting Algorithm simulates this cancellation process in a single pass using two variables: a candidate and a count. The count represents how many "uncancelled" supporters the current candidate has.

  • When we see the same element as the current candidate, the candidate gains a supporter (count++).
  • When we see a different element, one supporter cancels out (count--).
  • When the count reaches zero, all supporters have been cancelled. We pick the next element as a fresh candidate.

The majority element survives this process because it has more supporters than all other elements combined — they simply cannot all be cancelled out.

Step-by-Step Explanation

Let's trace through with nums = [2, 2, 1, 1, 1, 2, 2]:

Step 1: Initialize candidate = none, count = 0.

Step 2: Process nums[0] = 2. Count is 0, so set candidate = 2, count = 1.

Step 3: Process nums[1] = 2. Element matches candidate. Increment count to 2.

Step 4: Process nums[2] = 1. Element differs from candidate (2). Decrement count to 1. One pair of (2, 1) cancels out.

Step 5: Process nums[3] = 1. Element differs from candidate (2). Decrement count to 0. Another cancellation. All uncancelled support for candidate 2 is exhausted.

Step 6: Process nums[4] = 1. Count is 0, so set candidate = 1, count = 1. Fresh start.

Step 7: Process nums[5] = 2. Element differs from candidate (1). Decrement count to 0. Pair (1, 2) cancels. Candidate 1 loses all support.

Step 8: Process nums[6] = 2. Count is 0, so set candidate = 2, count = 1.

Step 9: Scan complete. The surviving candidate is 2. Return 2.

Boyer-Moore Voting — Cancellation Until One Candidate Survives — Watch how the candidate and count change as elements support or oppose the current candidate. The majority element always survives because it cannot be fully cancelled out.

Algorithm

  1. Initialize candidate to any value and count to 0.
  2. For each element nums[i]:
    a. If count == 0, set candidate = nums[i] and count = 1.
    b. Else if nums[i] == candidate, increment count.
    c. Else (nums[i] ≠ candidate), decrement count.
  3. Return candidate.

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
};
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = 0
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
                count = 1
            elif num == candidate:
                count += 1
            else:
                count -= 1
        return candidate
class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once, performing O(1) work (a comparison and an increment or decrement) per element. Total: n iterations × O(1) = O(n).

Space Complexity: O(1)

We use only two variables: candidate and count. No data structures grow with input size. This meets the follow-up challenge of solving the problem in linear time with constant extra space.

The Boyer-Moore Voting Algorithm is optimal in both time and space for this problem.