Skip to main content

12. Majority Element

easyAsked at Nubank

Find the element that appears more than n/2 times in an array — Nubank uses Boyer-Moore voting as a proxy for streaming-fraud aggregation patterns.

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

Problem

Given an array nums of size n, return the majority element — the element that appears strictly more than floor(n / 2) times. You may assume the majority element always exists.

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • A majority element is guaranteed to exist

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 count

Count occurrences in a Map, return the first key past n/2.

Time
O(n)
Space
O(n)
function majorityElement(nums){ const m=new Map(); for(const n of nums){ m.set(n,(m.get(n)||0)+1); if(m.get(n)>nums.length/2) return n; } }

Tradeoff:

2. Boyer-Moore voting

Keep a candidate and a count; increment if equal, decrement otherwise. The majority survives because it out-cancels every other group combined.

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

Tradeoff:

Nubank-specific tips

Nubank engineers reward the O(1)-space answer; tie it to streaming aggregations over a Kafka card-auth feed where you cannot afford a per-key map.

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 Nubank interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →