AlgoViz
HomeArrays & Hashing

Majority Element-I

Easy

Boyer-Moore vote cancelling

Problem

Given an integer array nums of size n, return the majority element of the array. The majority element of an array is an element that appears more than n/2 times in the array. The array is guaranteed to have a majority element.

In simple words

Use Moore voting: keep a candidate and a count, flipping candidate when the count hits zero.

The idea

Hold a candidate and a counter: matching elements increment it, differing ones decrement it, and a zero counter adopts the next element. Because the majority element occurs more than n/2 times it cannot be fully cancelled by everything else combined, so it survives as the candidate.

The trick

  • Only correct when a majority is guaranteed — otherwise verify with a second counting pass.
  • The counter is a cancellation tally, not a frequency.
  • O(n) time, O(1) space, versus O(n) space for a frequency map.
2
2
1
1
2
2
0
1
2
3
4
5

Step 1 of 3. Brute force: count each number until one appears more than n/2 times. Values: 2, 2, 1, 1, 2, 2.

1/3
Brute force
timeO(n²)spaceO(1)

Count each number.

1for (let i = 0; i < n; i++) {2  let count = 0;3  for (let j = 0; j < n; j++) if (nums[j] === nums[i]) count++;4  if (count > n / 2) return nums[i];5}

Input

array
[2, 2, 1, 1, 2, 2]

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [2, 2, 1, 1, 2, 2]
Output:
2
Explanation:
2 appears 4 times out of 6 — more than half.

Example 2

Input:
nums = [3, 3, 3, 1]
Output:
3
Explanation:
3 shows up 3 of 4 times.

Example 3

Input:
nums = [1]
Output:
1
Explanation:
The only element is trivially the majority.

Constraints

  • n == nums.length.
  • 1 <= n <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • One value appears more than n/2 times.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.