Skip to main content

13. Majority Element

easyAsked at Intuit

Given an array of size n, find the element that appears more than n/2 times. Intuit asks this to test whether you know Boyer-Moore voting versus reaching for a hash count, and whether you handle the tax-bracket-style 'most common category' framing.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q2)— Intuit QuickBooks SWE screen, framed as 'find the dominant tax category in a return.'
  • LeetCode Discuss (2025-12)— Intuit phone screen — interviewer pushed for O(1) space after hash map.

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 count

Count frequencies and return the key whose count exceeds 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: Linear time but uses O(n) space. The follow-up question is always: can you do O(1) space?

2. Boyer-Moore voting (optimal)

Maintain a candidate and a counter. Increment when you see the candidate, decrement otherwise; reset the candidate when the counter hits zero. The majority survives.

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

Tradeoff: Linear time, constant space. The intuition: every non-majority element can cancel at most one majority occurrence.

Intuit-specific tips

Intuit interviewers expect you to walk through why Boyer-Moore works — pairs of (majority, non-majority) cancel, but majority by definition exceeds n/2, so survives. They probe the variant where 'majority' isn't guaranteed; you'd need a second pass to verify. Bonus: mention that this generalizes to finding all elements appearing more than n/3 times (LC 229) with two candidates.

Common mistakes

  • Forgetting to reset the candidate when count drops to zero.
  • Using > nums.length / 2 with integer division and getting off-by-one edge cases.
  • Assuming a verification pass is unnecessary when the problem guarantees the majority exists — only safe when explicitly promised.

Follow-up questions

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

  • Majority Element II — find all elements appearing more than n/3 times (LC 229).
  • What if the majority is not guaranteed to exist? (Add verification pass.)
  • How would you parallelize this for a distributed dataset?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What if the array has no majority?

Boyer-Moore returns the last 'surviving' candidate, which may not actually be a majority. Add a verification pass that counts occurrences of the candidate and confirms > n/2.

How does this relate to tax bracket lookups at Intuit?

Conceptually similar: you scan transactions and identify the dominant bracket. The algorithm changes (bracket lookup is a range tree), but the 'find the dominant category in one pass' framing is the same.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →