Majority Element

Difficulty: easy

Problem

Given an integer 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.

**What does 'more than n/2 times' mean?** - If n = 7, then n/2 = 3 - The majority element must appear at least 4 times

Example

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: 2 appears 4 times, 1 appears 3 times. Array size = 7. Since 4 > 7/2, the majority element is 2.

Brute-force approach

For each element, count how many times it appears in the entire array. If the count exceeds n/2, that element is the majority.

Steps

  1. For each element in the array (outer loop)
  2. Count its occurrences by scanning entire array (inner loop)
  3. If count > n/2, return that element
  4. Move to next element if threshold not met

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Nested loops make it O(n²) - very slow for large arrays
  • We may count the same element multiple times
  • Doesn't leverage the mathematical property of majority

Optimal approach

Key insight: If an element occurs more than half the time, it cannot be completely canceled out by other elements. Think of it as votes: the majority always survives.

Boyer-Moore Voting Algorithm: Maintain a candidate and a count. Same element increases count, different element decreases it. When count hits 0, pick a new candidate.

Steps

  1. Initialize count = 0, candidate = null
  2. For each element in the array:
  3. - If count == 0, set current element as candidate
  4. - If element == candidate, increment count
  5. - Else, decrement count
  6. Return the candidate

Time complexity: O(n) · Space complexity: O(1)