Skip to main content

8. Majority Element

easyAsked at Rappi

Find the element that appears more than half the time in an array — Rappi frames this as finding the dominant pickup zone in a streaming feed of courier check-ins.

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

Problem

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

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • The majority element 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

Tally occurrences in a map and return the key exceeding n/2.

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

Tradeoff:

2. Boyer-Moore vote

Maintain a candidate and a counter; increment on match, decrement otherwise — survivor is the majority.

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

Tradeoff:

Rappi-specific tips

Rappi rewards Boyer-Moore here because their streaming check-in pipeline cannot afford an O(n) map allocation per minute window.

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

Practice these live with InterviewChamp.AI →