Skip to main content

8. Majority Element

easyAsked at Byju's

Find the element appearing more than n/2 times in an array.

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. You may assume that the majority element always exists in the array.

Constraints

  • 1 <= n <= 5 * 10^4
  • Majority element always exists

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 frequencies and return whichever exceeds n/2.

Time
O(n)
Space
O(n)
const m=new Map();
for(const n of nums) m.set(n,(m.get(n)||0)+1);
for(const [k,v] of m) if(v>nums.length/2) return k;

Tradeoff:

2. Boyer-Moore vote

Maintain a candidate and counter; matching ballots increment, opposing ballots decrement. Whenever count hits zero, swap candidates.

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

Tradeoff:

Byju's-specific tips

Byju's recommendation engineers respect candidates who connect Boyer-Moore voting to majority-class detection in adaptive-learning recommendations.

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 Byju's interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →