Majority Element

Difficulty: easy

Problem

Given an integer array `nums` with `n` entries, find the value that occurs strictly more than ⌊n / 2⌋ times. It is guaranteed that such a value exists, and you return it.

**What does 'more than n/2 times' mean?** - If n = 7, then n/2 = 3 - The majority element must appear at least 4 times

Example

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: The array has 7 entries; 2 occurs 4 times and 1 occurs 3 times. Only 2 beats the threshold of 3, so 2 is the majority element.

Brute-force approach

For each element, count how many times it appears in the entire array. If the count exceeds n/2, that element is the majority.

Steps

  1. For each element in the array (outer loop)
  2. Count its occurrences by scanning entire array (inner loop)
  3. If count > n/2, return that element
  4. Move to next element if threshold not met

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Nested loops make it O(n²) - very slow for large arrays
  • We may count the same element multiple times
  • Doesn't leverage the mathematical property of majority

Optimal approach

Key insight: If an element occurs more than half the time, it cannot be completely canceled out by other elements. Think of it as votes: the majority always survives.

Boyer-Moore Voting Algorithm: Maintain a candidate and a count. Same element increases count, different element decreases it. When count hits 0, pick a new candidate.

Steps

  1. Initialize count = 0, candidate = null
  2. For each element in the array:
  3. - If count == 0, set current element as candidate
  4. - If element == candidate, increment count
  5. - Else, decrement count
  6. Return the candidate

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function majorityElement(nums):
    // Boyer-Moore Voting Algorithm
    count = 0
    candidate = null
    
    for each num in nums:
        if count == 0:
            candidate = num
        
        if num == candidate:
            count++
        else:
            count--
    
    return candidate

Hints

  • Think about voting: same element = +1 vote, different = -1 vote
  • When count reaches 0, pick a new candidate
  • The majority element will always be the last candidate standing

Complexity questions

What is the time complexity of the brute force approach?

O(n²). The brute force uses nested loops: for each element (n), we count occurrences (n), giving O(n × n) = O(n²).

What is the time complexity of the optimal voting approach?

O(n). The optimal voting approach makes a single pass through the array, visiting each element once: O(n).

What is the space complexity of the optimal voting approach?

O(1). We only use two variables (candidate and count), regardless of array size: O(1) constant space.

Check your understanding of Majority Element

What is the definition of a majority element?

An element that appears more than n/2 times. A majority element must appear MORE than ⌊n/2⌋ times. For an array of size 7, this means more than 3 times (at least 4 times).

In the array [3, 3, 4, 2, 4, 4, 2, 4, 4], what is the majority element?

4. The array has 9 elements. 4 appears 5 times. Since 5 > 9/2 = 4.5, 4 is the majority element.

Related problems

Keep practising