DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Majority Element

easyArrays and hashing

Problem statement

You are given a list of integers nums of length n. One value appears more than n / 2 times (strictly more than half). Return that value. You can assume it always exists.

Examples

Example 1

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

Output: 5

Explanation: 5 appears 3 times out of 5, which is more than half.

Example 2

Input: nums = [6, 6, 3]

Output: 6

Explanation: 6 appears 2 times out of 3.

Hints

Approach

This is the Boyer-Moore voting algorithm. Keep one candidate and a count. A matching value adds a vote, a different value removes one. When the count hits zero, the next value becomes the new candidate.

  1. Start with count = 0.
  2. For each x: if count is 0, set candidate = x.
  3. Add 1 to count if x == candidate, otherwise subtract 1.
  4. Return candidate.

Why it works: every time a vote is removed, one majority value and one other value cancel each other out. The majority has more than half the values, so it cannot be fully cancelled and it is the candidate left at the end.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def majorityElement(self, nums: list[int]) -> int:
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate

Follow-up questions

  • Find every value that appears more than n / 3 times, in O(1) extra space.
  • Values arrive as a stream. Can you report the current majority candidate after each one?

Frequently asked questions

Boyer-Moore still gives you the only possible candidate, but it might not be a real majority. Make a second pass to count the candidate and check it really appears more than n / 2 times.

Yes. A value that fills more than half of a sorted list must cover index n // 2. It is O(n log n) time, simpler to explain, and a reasonable answer to mention before Boyer-Moore.

Voting shows up in distributed systems: several replicas report a value and you want the one most of them agree on. Boyer-Moore is also handy for spotting a dominant key in a stream, such as one client sending most of the traffic, without storing a count per key.