Skip to main content

4. Majority Element

easyAsked at Confluent

Return the element appearing more than n/2 times — Confluent uses it to test Boyer-Moore voting, which maps cleanly to streaming heavy-hitters over a Kafka topic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of size n, return the majority element — the value that appears more than n/2 times. You may assume the array always has a majority element.

Constraints

  • n == nums.length
  • 1 <= n <= 5*10^4
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input
nums=[3,2,3]
Output
3

Example 2

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

Approaches

1. Hash map count

Count occurrences and return the key whose count exceeds n/2.

Time
O(n)
Space
O(n)
const c=new Map();
for (const x of nums) c.set(x,(c.get(x)||0)+1);
for (const [k,v] of c) if (v>nums.length/2) return k;

Tradeoff:

2. Boyer-Moore vote

Maintain a candidate and a counter; increment when match, decrement when not. When the counter hits zero pick a new candidate. The survivor wins.

Time
O(n)
Space
O(1)
function majorityElement(nums) {
  let cand = 0, count = 0;
  for (const x of nums) {
    if (count === 0) cand = x;
    count += (x === cand) ? 1 : -1;
  }
  return cand;
}

Tradeoff:

Confluent-specific tips

Confluent loves when you connect Boyer-Moore to ksqlDB heavy-hitter queries — bonus signal if you mention partition assignment means you need one voter per consumer to keep state local.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Majority Element and other Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →