Skip to main content

22. Majority Element

easyAsked at Salesforce

Find the element that appears more than n/2 times in an array. Salesforce asks this to test the Boyer-Moore voting algorithm, an O(1)-space trick that surprises most candidates.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce data-team uses Boyer-Moore in stream-of-events processing.
  • LeetCode Discuss (2025-11)— Asked specifically to test if candidates know Boyer-Moore.

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 count

Count occurrences, return any value with count > n/2.

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

Tradeoff: O(n) space. Salesforce will push you to O(1).

2. Boyer-Moore voting

Maintain a candidate and a count. On match, count++. On mismatch, count--. When count = 0, swap candidate. The majority always wins.

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: O(1) space. The majority element's vote always exceeds the total of all others combined, so it always survives the cancellation game.

Salesforce-specific tips

Salesforce specifically tests Boyer-Moore because it's the canonical 'clever O(1) space trick' and they want to see if you've seen it. Bonus signal: articulate the cancellation argument — every non-majority element cancels with exactly one majority vote, and majority always has more than half, so the residue is always the majority.

Common mistakes

  • Returning candidate without explaining why it works — Salesforce wants the proof, not just the code.
  • Forgetting to increment count when we re-affirm the same candidate — gives wrong dynamic.
  • Assuming majority always exists but coding for the general case — wasted complexity if it's guaranteed.

Follow-up questions

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

  • Majority Element II (LC 229) — elements appearing more than n/3 times (at most 2 such).
  • Verify a candidate is majority (when not guaranteed).
  • Find majority in a stream (online algorithm).

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 battle. Every non-majority vote cancels one majority vote. Since majority has > n/2 votes, even after maximal cancellation, at least one majority vote survives — so the candidate at the end is the majority.

What if no majority exists?

The algorithm still returns some candidate, but it may not be a true majority. Always do a second pass to verify if the existence isn't guaranteed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →