Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimal

Majority Element I

The problem asks for the element that appears strictly more than n/2 times in an array. For example, in an array of 8 elements, a majority element must appear at least 5 times. There can be at most one majority element.

The video presents three solutions, from brute force to the optimal approach.

1. Brute-force solution

For each element in the array, scan the entire array and count its occurrences. Return the element if its count is greater than n/2. If no element meets the condition, return a suitable “not found” value, such as -1.

• Time: O(n²)
• Extra space: O(1)

2. Better solution: Hashing

Use a map where each key is an array element and its value is that element’s frequency. Traverse the array to build the frequency map, then return the first element whose frequency is greater than n/2.

• Time: Typically O(n log n) with an ordered map; typically O(n) on average with an unordered map, though its worst case can be worse.
• Extra space: O(n) in the worst case.

3. Optimal solution: Moore’s Voting Algorithm

A majority element occurs more times than all other elements combined, so pairing different values against each other cannot completely cancel it out. If a majority element exists, it remains as the final candidate.

Candidate-selection pass

Maintain two variables:

• candidate — the current potential majority element
• count — a balance, not the candidate’s actual frequency

Process each array value:

1. If count is 0, set the current value as the candidate and set count to 1.
2. Otherwise, if the current value equals the candidate, increment count.
3. If it differs, decrement count.

When different values cancel each other, a count of zero means the next value starts a new candidate group. At the end of this pass, the remaining candidate is the only possible majority element, but it is not necessarily confirmed.

Verification pass

Scan the array again and count the candidate’s actual occurrences. Return it only if its frequency is greater than n/2; otherwise, report that no majority element exists.

Verification is necessary when the input is not guaranteed to contain a majority element. If the problem guarantees that one exists, the candidate can be returned without a second scan.

• Time: O(n) overall
• Extra space: O(1)

Speakers and sources

• Speaker: One presenter or instructor from Take U Forward; the presenter’s name is not stated in the subtitles.
• Materials mentioned: A C++ code editor or demo and a course sheet or problem link. The presenter says Java and Python versions are available in the description, but those versions are not shown in the subtitles.