Skip to main content

6. Majority Element

easyAsked at Revolut

Find the value appearing more than n/2 times, a Revolut warm-up that mirrors detecting the dominant currency in a stream of FX trades.

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

Problem

Given an array nums of size n, return the majority element which appears more than n/2 times. You may assume the majority element always exists in the array.

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • Majority element always exists

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 and return whichever crosses n/2.

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

Tradeoff:

2. Boyer-Moore voting

Maintain a candidate and count; non-majority cancel out pairwise. Constant space.

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:

Revolut-specific tips

Revolut interviewers love Boyer-Moore here because it mirrors streaming FX-pair aggregation — explicitly state the algorithm requires the majority to actually exist or a second verification pass is needed.

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

Practice these live with InterviewChamp.AI →