Skip to main content

4. Majority Element

easyAsked at Redis

Find the element that appears more than n/2 times; Redis interviewers use it to test Boyer-Moore voting, a constant-space pattern that maps onto stream-processing.

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

Problem

Given an array nums of size n, return the majority element which appears more than n/2 times. Assume the majority element always exists in the array.

Constraints

  • 1 <= n <= 5 * 10^4
  • 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 with a map.

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

Tradeoff:

2. Boyer-Moore voting

Maintain a candidate and a count; cancel on mismatch. Constant space makes it ideal for unbounded streams Redis Streams might feed.

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

Tradeoff:

Redis-specific tips

Redis loves Boyer-Moore here because it shows you can spot constant-memory streaming algorithms, the same DNA as their HyperLogLog approximate counters.

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

Practice these live with InterviewChamp.AI →