169. Majority Element
#array #moores_voting_algorithm
Given an array find the element that appears more than times ( assume such majority element always exists in the array )
Solve this problem in linear time using constant space
Intuition
We can use the simple voting mechanism where anything different is considered a vote against.
Only the majority element will have vote in his favour.
Approach
Track the
candidate
& the number ofvote
i.e its occurrence.If we encounter an element different from the
candidate
decrease thevote
countIf for the current
candidate
thevotes
become0
replace it
At the end only the max occurring element will remain.
Complexity
Space Complexity
Time Complexity
No extra space is needed
Code
Last updated