Finding the majority element
only for case where majority has more than n/2 occurrences
The Boyer-Moore voting method determines the majority element i.e with more than occurrences among other elements.
If there is no majority, the algorithm will not recognise this and will continue to output one of the items. To avoid this we can add a check
Algorithm
First pass identifies an element as a majority
Second pass confirms that the element identified in the first pass is indeed a majority
Complexity
Time Complexity :
Only 2 iteration are made over the array
Space Complexity :
No extra space is needed
Reference
Last updated