Majority Element
- mosesg1123
- Apr 18
- 3 min read
Updated: Apr 22
Finding the majority element—an item that appears more than half the time in an array—is a classic warm‑up that’s surprisingly useful in real data analysis: think consensus detection in voting systems or dominant signals in sensor data. Let me walk you through how I’d tackle this live in a technical interview.
Problem Statement
Given an integer array nums of size n, return the majority element: the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
1. Clarify Requirements Before Jumping Into Code
I’ll check a few details first
The majority element is guaranteed to exist? Yes.
Array contains integers only? Yes.
Negative numbers or zeros allowed? Yes, any integer.
What should I return—value or index? Value.
Can I modify the array? It doesn’t matter, but I’ll aim for non‑destructive.
2. Identify the Category of the Question
This is an array problem with an element frequency or voting pattern. At its simplest it’s about counting occurrences; at its most elegant it’s about tracking a running candidate without extra memory. Recognizing that hints at the Boyer‑Moore Voting Algorithm.
3. Consider a Brute‑Force Approach to Understand the Problem
The simplest idea: for each unique element, count how many times it appears (nested loops or a set of unique values). Return whichever count exceeds n/2. That’s O(n²) with nested loops, or O(n²) in worst-case unique enumeration—too slow for large arrays.
4. Brainstorm More Solutions
Hash Map Count: One pass to build counts in a dictionary, second pass (or on the fly) to find the element > n/2. O(n) time, O(n) space.
Sorting: Sort the array and return nums[n//2]. Sorting is O(n log n) time, O(1) space if in place. The middle element is guaranteed to be the majority.
Boyer‑Moore Voting: Maintain a candidate and count. Iterate once: if count is zero, pick current element as candidate; then increment or decrement count based on whether current equals candidate. At the end, candidate is the majority. O(n) time, O(1) space.
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Hash Map Count | O(n) | O(n) | Simple, easy to implement | Uses extra memory |
Sorting | O(n log n) | O(1)–O(n) | Minimal code, leverages built‑ins | Slower than O(n), modifies array |
Boyer‑Moore Voting | O(n) | O(1) | Best time and space, elegant | Requires understanding algorithm |
Given the guarantee that a majority exists, Boyer‑Moore is ideal for O(1) space and O(n) time.
6. Write Pseudocode to Structure Your Thoughts
function majorityElement(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -= 1
return candidate
7. Consider Edge Cases
Single element array, e.g. [7] → returns 7
All elements the same, e.g. [2,2,2] → returns 2
Majority element at start, e.g. [3,3,1,2,3] → returns 3
Majority element at end, e.g. [1,1,2,1] → returns 1
Large array with alternating values but one majority, e.g. [4,5,4,6,4,7,4] → returns 4
8. Write Full Code Syntax
def majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
9. Test Your Code
assert majority_element([3, 2, 3]) == 3
assert majority_element([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_element([7]) == 7
assert majority_element([1,1,1,2,3,1]) == 1
assert majority_element([4,5,4,6,4,7,4]) == 4
print("All tests passed!")
10. Key Lessons to Remember for Future Questions
When a problem asks for an element appearing more than half the time, think Boyer‑Moore Voting for O(1) space. Remembering key algorithms like Boyer-Moore will help you stand out from the crowd!
Hash maps are a safe first step, but watch for space trade‑offs. If you can't remember the Boyer-Moore algorithm though, you can always fall back to the next best option.
Clear, concise candidate/count logic often outperforms bulky data structures.
Good Luck and Happy Coding!
Comments