How to Solve Majority Element on LeetCode
The Majority Element problem is a classic LeetCode question that tests your understanding of arrays, voting algorithms, and frequency counting.
Problem Statement
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. Assume that the array is non-empty and the majority element always exists.
Example:
Input: nums = [3,2,3]
Output: 3
Why This Problem Matters for Interviews
This problem:
- Introduces efficient frequency counting
- Features the Boyer-Moore Voting Algorithm
- Forms a basis for advanced frequency/majority logic
Approaches to Majority Element
1. Hash Map Frequency
Count occurrences of each element.
Time Complexity: O(n)
Space Complexity: O(n)
def majorityElement(nums: list[int]) -> int:
counts = {}
for n in nums:
counts[n] = counts.get(n, 0) + 1
if counts[n] > len(nums) // 2:
return n
2. Boyer-Moore Voting Algorithm (Optimal)
Track a candidate and its count.
Time Complexity: O(n)
Space Complexity: O(1)
def majorityElement(nums: list[int]) -> int:
count, candidate = 0, None
for n in nums:
if count == 0:
candidate = n
count += (1 if n == candidate else -1)
return candidate
Key Interview Talking Points
- Why majority element must exist
- Tradeoff between extra space and optimal in-place algorithms
- Boyer-Moore's "voting" intuition
- Edge cases (odd vs even n, all same, all different except one)
Big O Complexity Recap
Approach | Time Complexity | Space Complexity |
---|---|---|
Hash Map | O(n) | O(n) |
Boyer-Moore | O(n) | O(1) |
Pro Interview Tips
- Mention that result is always guaranteed (per problem statement).
- Discuss how to extend to find elements > n/3 times.
- Practice with test cases