Skip to main content

23. Majority Element

easyAsked at Workday

Find the element that appears more than n/2 times. Workday uses this to evaluate whether you reach for Boyer-Moore voting — useful when reconciling 'which dept gets the most pay-grade adjustments'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

Problem

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

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • Follow-up: Could you solve the problem in linear time and in O(1) space?

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 each, return the one > 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: O(n) extra space — fails the follow-up.

2. Boyer-Moore voting

One candidate, one counter. If counter is 0, take current as candidate. If current == candidate, ++count. Else --count.

Time
O(n)
Space
O(1)
function majorityElement(nums) {
  let candidate = nums[0];
  let count = 0;
  for (const x of nums) {
    if (count === 0) candidate = x;
    if (x === candidate) count++;
    else count--;
  }
  return candidate;
}

Tradeoff: O(1) space. The intuition: every non-majority element can 'cancel' one majority vote. Since majority > n/2, it can't be fully cancelled.

Workday-specific tips

Workday wants you to mention Boyer-Moore by name and walk through the cancellation intuition. If they don't trust the result and ask 'what if a majority doesn't actually exist?', the follow-up is a second pass to verify the candidate.

Common mistakes

  • Returning the candidate without the second-pass verification if majority isn't guaranteed.
  • Confusing 'more than n/2' with 'at least n/2'.
  • Not knowing why it works — interviewer will press.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Majority Element II (LC 229) — elements appearing more than n/3.
  • Second-pass verification when majority isn't guaranteed.
  • Streaming version — only one pass through a generator.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Boyer-Moore work?

Think of it as a tournament. Every time a non-majority sneaks in, it cancels one majority vote. Since majority appears > n/2 times, even if all the others cancel, there's still at least one majority vote left at the end.

What if there's no majority?

The algorithm still returns SOMETHING — but it's not guaranteed to be a majority. Run a second pass to verify count > n/2.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →