Skip to main content

10. Majority Element

easyAsked at Baidu

Find the element that appears more than n/2 times in an array of length n.

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

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; assume the array is non-empty and the majority element always exists.

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • Majority element is guaranteed to exist

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

Tally counts; return the first key whose tally exceeds n/2.

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

Tradeoff:

2. Boyer-Moore voting

Track a candidate and a count; cancel out one of every pair of differing votes — survivor is the majority.

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

Tradeoff:

Baidu-specific tips

Baidu uses Boyer-Moore on streaming ad-ranking telemetry to flag the dominant click-source per minute, so they specifically test whether you know the O(1)-memory voting trick by name.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →