Mastery Points
0
Majority Element problem in dsa
Context & Logic
A majority element is an element that appears more than n/2 times in an array. The Boyer-Moore Voting Algorithm solves this in linear time.
Example
function majorityElement(nums) {
let candidate = null, count = 0;
for (let num of nums) {
if (count === 0) candidate = num;
count += (num === candidate) ? 1 : -1;
}
return candidate;
}Step-by-Step Logic
1
Maintain a candidate and a counter.
2
If count is 0, assign the current element as the candidate.
3
If current element matches candidate, increment count; otherwise, decrement.
4
The remaining candidate is the majority element (if one exists).
Complexity Metrics
Time Efficiency
O(n)
Memory Footprint
O(1)