AlgoMaster Logo

Majority Element

easyFrequency6 min readUpdated June 23, 2026

Understanding the Problem

We need to find the element that appears more than ⌊n / 2⌋ times in the array. The problem guarantees such an element exists, so we don't need to verify our answer, only find it.

The "more than n/2 times" condition has a useful consequence. The majority element occupies more than half the array, so no other element can also appear more than n/2 times. The majority element is therefore unique. This property is what makes the linear-time, constant-space algorithm later in this chapter possible.

Approach 1: Hash Map

Intuition

Count how many times each element appears, then return the one whose count exceeds n/2. A hash map gives O(1) lookups and updates for the counting.

We iterate through the array once, incrementing the count for each element. We can check the count right after each increment and return early the moment an element crosses the threshold, rather than counting everything first and scanning the map afterward.

Algorithm

  1. Create a hash map to store the count of each element.
  2. Iterate through the array. For each element, increment its count in the map.
  3. If the count for the current element exceeds n / 2, return that element immediately.
  4. If the loop finishes without returning (won't happen given the guarantee), return -1 as a fallback.

Example Walkthrough

1Initialize: threshold = 7/2 = 3, counts = {}
0
2
i
1
2
2
1
3
1
4
1
5
2
6
2
1/8

Code

This approach is correct but uses O(n) extra space. The next approach removes the hash map by exploiting the fact that the majority element appears more often than all others combined.

Approach 2: Sorting

Intuition

If you sort the array, the majority element always ends up at index n/2.

After sorting, equal values form one contiguous block. The majority element's block is longer than n/2 elements, so it must contain the middle index. If the majority element is the smallest value, its block runs from index 0 through at least n/2. If it is the largest, its block runs from at most n/2 to n-1. Either way, index n/2 falls inside the block.

So we sort and read the middle element. No counting needed.

Algorithm

  1. Sort the array.
  2. Return the element at index n / 2.

Example Walkthrough

1Original array, unsorted
0
2
1
2
2
1
3
1
4
1
5
2
6
2
1/6

Code

Sorting costs O(n log n) time, yet we only read one element afterward. The next approach finds the majority element in a single linear pass with O(1) space by using the "more than half" property to cancel out non-majority elements.

Approach 3: Boyer-Moore Voting Algorithm

Intuition

Walk through the array maintaining a "candidate" value and a counter. When the current element equals the candidate, increment the counter. When it differs, decrement the counter. When the counter reaches zero, the next element becomes the new candidate with a counter of 1. The candidate left at the end is the majority element.

Algorithm

  1. Initialize candidate to any value and count to 0.
  2. Iterate through each element in the array:
    • If count is 0, set the current element as the new candidate and set count to 1.
    • Otherwise, if the current element equals candidate, increment count.
    • Otherwise, decrement count.
  3. Return candidate.

Example Walkthrough:

1Initialize: candidate=?, count=0
0
2
i
1
2
2
1
3
1
4
1
5
2
6
2
1/8

Code

Whenever the counter resets to zero, the processed prefix contains an equal number of candidate and non-candidate elements. Discarding that prefix leaves the rest of the array, and the majority element of the full array remains the majority of what is left, because removing equal counts of two values cannot flip which value is in the majority. The algorithm effectively peels off these balanced prefixes until only the true majority element remains.