Majority Element
Problem
Given an integer array nums of size n, return the majority element, which is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
- 1 ≤ nums.length ≤ 5 * 10⁴
- −10⁹ ≤ nums[i] ≤ 10⁹
- The majority element always exists in the array
Example
nums = [2,2,1,1,1,2,2]2A brute-force approach would count the frequency of each element and return the one with count greater than n/2. For the input, 2 appears 4 times and 1 appears 3 times. The algorithm uses a voting mechanism to track a candidate and its count. Initially, candidate is None and count is 0. Iterating through nums: at first 2, count is 0 so candidate becomes 2 and count increments to 1. Next 2 matches candidate, count increments to 2. Next 1 does not match candidate, count decrements to 1. Next 1 again does not match candidate, count decrements to 0. When count reaches 0, candidate updates to next element 1, count increments to 1. Next 2 does not match candidate, count decrements to 0. Next 2 updates candidate to 2, count increments to 1. Next 2 matches candidate, count increments to 2. At the end, candidate is 2, which is the majority element.
Approach
Straightforward Solution
A brute-force approach counts the frequency of each element using a hash map and returns the element with count > n/2. This requires O(n) time and O(n) space, which is acceptable but not optimal in space.
Core Observation
The majority element appears more than half the time, so it cannot be completely canceled out by other elements. This guarantees that a voting mechanism that increments count for the candidate and decrements for others will end with the majority element as the candidate.
Path to Optimal
PreviewThe key insight is that since the majority element appears more than half the time, it can be found by pairing off different elements and canceling them out. The Boyer-Moore Voting Algorithm exploits this by maintaining a candidate and a count…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the array, maintaining a candidate and a count. When count is zero, set the candidate to the current element…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm makes a single pass through the array, performing constant time operations per element.
Space
O(1)
Only two variables (candidate and count) are maintained regardless of input size, resulting in constant auxiliary space.
Pattern Spotlight
Greedy Algorithms (Boyer-Moore Voting)
When a majority element exists, pairing off different elements and canceling them leads to the majority element surviving; tracking a candidate and count with increments and decrements efficiently finds it in one pass with constant space.
Solution
| 1 | class Solution: |
| 2 | def majorityElement(self, nums: List[int]) -> int: |
| 3 | |
| 4 | candidate = None |
| 5 | count = 0 |
| 6 | |
| 7 | for n in nums: |
| 8 | |
| 9 | if count == 0: |
| 10 | candidate = n |
| 11 | |
| 12 | if n == candidate: |
| 13 | count += 1 |
| 14 | else: |
| 15 | count -= 1 |
| 16 | |
| 17 | return candidate |
Step-by-Step Solution
Initialize Candidate and Count to Track Majority Element
| 4 | candidate = None |
| 5 | count = 0 |
Objective
To set up variables that will hold the current candidate for majority and its vote count.
Key Insight
Starting with no candidate and zero count allows the algorithm to assign the first element as candidate and begin counting votes. This initialization is critical because it sets the baseline for the voting process that follows.
Interview Quick-Check
Core Logic
Candidate and count variables maintain the current majority candidate and its relative vote count.
State & Boundaries
Count starts at zero to indicate no current candidate, triggering candidate assignment on first iteration.
Iterate Through Array to Update Candidate and Vote Count
To process each element, updating the candidate and count according to the Boyer-Moore voting rules.
Return the Final Candidate as the Majority Element
To output the candidate that survived all cancellations as the majority element.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if count == 0:Check if count has dropped to zero to reset candidate.
Resetting the candidate when count reaches zero is the critical step that allows the algorithm to discard invalid candidates and focus on the true majority element.
count -= 1Decrement count when current element differs from candidate.
This decrement is the core of the Boyer-Moore algorithm's cancellation logic, enabling the majority element to prevail by offsetting votes from minority elements.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why does the Boyer-Moore Voting Algorithm guarantee that the candidate at the end is the majority element?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Majority Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Majority Element drill