Skip to main content

12. Majority Element

easyAsked at Coupang

Find the element that appears more than n/2 times, mirroring how Coupang's same-day delivery routing identifies the dominant origin warehouse per zone.

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

Problem

Given an array nums of size n, return the element that appears more than floor(n/2) times. The majority element is guaranteed to exist.

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

Tally each element; return the first whose count exceeds n/2.

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

Tradeoff:

2. Boyer-Moore vote

Maintain a candidate and counter; increment on match, decrement otherwise. Candidate at end is the majority.

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:

Coupang-specific tips

Coupang same-day delivery routing identifies the dominant origin fulfillment center per zip; Boyer-Moore's O(1) memory matches how their dispatcher batches in constant memory.

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

Practice these live with InterviewChamp.AI →