Majority Element II (Boyer‐Moore Voting Algorithm) - yangbnu/LeetcodeSelf GitHub Wiki

Majority Element II https://algo.monster/liteproblems/229

We initiate two potential candidates for the majority element, m1 and m2, with placeholders that don't match any elements in the array to start with. These candidates represent the two elements we think might be appearing more than ⌊ n/3 ⌋ times.

Similarly, we have two counters, n1 and n2, that help us keep track of the number of times we have encountered m1 and m2 in the array.

We iterate through the array (nums). For each element (m), we do the following:

If m is equal to one of our current candidates (m1 or m2), we increment the respective counter (n1 or n2). If one of the counters is at zero, it means the respective candidate is not a valid majority element or has been 'voted out', so we replace it with the current element m and set its counter to 1. If m is not matching either candidate and both counters n1 and n2 are not zero, we decrement both counters. This is analogous to 'voting out' a candidate, as there must be at least three distinct numbers in the current sequence (thus each couldn't be more than ⌊ n/3 ⌋ appearances). Since the counters can be manipulated by elements that are not actually the desired majority elements, we make a final pass through the array to check whether our candidates truly occur more than ⌊ n/3 ⌋ times. We construct the result list by only including candidates that meet this criterion.