Skip to main content

22. Majority Element

easyAsked at Plaid

Find the element that appears more than n/2 times in an array. Plaid asks this because identifying the dominant merchant category across a user's transactions has the same shape.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid data-engineering screen.
  • LeetCode Discuss (2026)— Plaid OA.

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

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 counting

Count occurrences; return the one > n/2.

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

Tradeoff: Works but uses O(n) extra space. Mention as the obvious starting approach.

2. Boyer-Moore voting

Single pass: maintain a candidate and a count. If count hits 0, pick a new candidate. If the next element matches, increment; else decrement. The majority wins by construction.

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: Constant space, single pass. The voting metaphor (pairs cancel out) is elegant — Plaid loves this when you can explain it crisply.

Plaid-specific tips

Plaid grades this on whether you reach for Boyer-Moore when O(1) space is preferred. Bonus signal: explain the voting metaphor — each non-majority element cancels one majority vote, and since majority > n/2, at least one majority vote survives. Connect it to streaming category counts where you can't store all transactions.

Common mistakes

  • Updating candidate when count > 0 — the algorithm only changes candidate when count is 0.
  • Forgetting to do the comparison after incrementing — order matters.
  • Trying sort()[n/2] — works for this specific problem but doesn't generalize and is O(n log n).

Follow-up questions

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

  • What if there's no guaranteed majority? Verify with a second pass.
  • Find all elements that appear > n/3 times (LC 229) — Boyer-Moore generalizes.
  • Stream version with bounded memory.

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 pairs (one majority, one non-majority) cancelling out. After cancellation, at least one majority element survives because majority > n/2.

What if the input has no majority?

The algorithm returns some candidate but it's not guaranteed correct. You'd need a verification pass. The LC problem guarantees a majority exists.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →