Skip to main content

169. Majority Element

easy

Find the element that appears more than n/2 times in an array. Three textbook solutions: hash count, sort and pick the middle, or Boyer-Moore voting in O(n) time and O(1) space.

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. Follow-up: Could you solve the problem in linear time and in 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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash count: count every element, return the one with count > n/2. O(n) time, O(n) space.

Hint 2

Sort: after sorting, the majority element (appears > n/2 times) must occupy position n/2. O(n log n) time, O(1) space if in-place.

Hint 3

Boyer-Moore Voting Algorithm: maintain a candidate and a count. Walk the array: if count == 0, set candidate = current. If current == candidate, count++; else count--.

Hint 4

After the pass, candidate is the majority. The algorithm pairs off elements; the majority's surplus survives.

Solution approach

Reveal approach

Boyer-Moore Voting Algorithm. Maintain candidate = None and count = 0. For each num in nums: if count == 0, set candidate = num and count = 1; else if num == candidate, count++; else count--. Return candidate. Why it works: every time the candidate is the majority, count goes up; every other element decrements it. Because the majority appears > n/2 times, its count can never be fully canceled — the surviving candidate is the majority. O(n) time, O(1) space. Sort-and-pick alternative is one line: return sorted(nums)[n // 2]. Both are interview-grade; Boyer-Moore is the answer for the linear-time follow-up.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • math
  • boyer-moore-voting
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg
  • Adobe

Practice these live with InterviewChamp.AI

Drill Majority Element and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →