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 Sam K., 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

More Math practice problems

See all Math problems →