Skip to main content

23. Majority Element

easyAsked at Datadog

Find the element that appears more than n/2 times. Datadog asks this because the Boyer-Moore vote algorithm is the canonical streaming-aggregate pattern for finding a heavy hitter in one pass with O(1) memory.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded explicitly on Boyer-Moore.
  • Blind (2025-12)— Recurring Datadog problem on streaming aggregates.

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. Implement it in O(n) time and O(1) space.

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. Hashmap count

Count occurrences; return the one with count > n/2.

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

Tradeoff: O(n) space — violates the constraint. Datadog will push for O(1).

2. Boyer-Moore voting (optimal)

Track a candidate and a count. Increment count on a match, decrement on a mismatch. When count hits 0, swap candidate.

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

Tradeoff: O(1) state. Streaming-safe — works on an unbounded stream. The canonical heavy-hitter sketch in Datadog's metric ingestion.

Datadog-specific tips

Datadog will follow up with: 'What if the majority element might NOT exist? Verify your answer.' Show that a second O(n) pass to count the candidate's occurrences is required. Bonus: extend to k-majority (Misra-Gries) for items appearing more than n/k times.

Common mistakes

  • Forgetting to handle the count-0-swap step — the algorithm depends on swapping candidate when count drains.
  • Returning the candidate WITHOUT a verification pass when existence isn't guaranteed.
  • Tracking multiple candidates without understanding the k-majority generalization.

Follow-up questions

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

  • Majority Element II (LC 229) — find elements appearing > n/3 times.
  • Misra-Gries sketch — k-majority generalization.
  • Heavy-hitter detection in a streaming metric ingest.

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?

Each pair of differing elements cancels out via the count decrement. The majority element appears more than n/2 times, so even worst-case cancellation leaves it as the final candidate.

What if there's no majority?

The algorithm returns SOME element, possibly wrong. A verification pass (count == > n/2) is mandatory when the majority isn't guaranteed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →