Given an array of n integers in which one value appears more than n / 2 times, return that value.
Before you code
There are at least four correct solutions, and each has a different cost profile. Work out the best, average and worst case of each before picking one:
- count every value in a hash map;
- sort the array and take the middle element;
- pick a random element and check whether it is the majority, repeating until it is;
- the Boyer-Moore vote, in one pass with two variables.
Hints
- The random guess succeeds with probability above 1/2 each try, so the expected number of tries is under 2: expected O(n). Its worst case is unbounded, though.
- For Boyer-Moore, keep a
candidateand acount. Ifcountis 0, take the current value as the candidate. Add 1 when the value matches the candidate and subtract 1 when it doesn't. - Each non-majority value can cancel at most one majority value, and there aren't enough of them to cancel them all, so the majority is the candidate left at the end.
Production & complexity notes
When solving Majority element on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Best, average and worst case to reinforce the underlying pattern.
What it practices
Comparing best, average, expected and worst cases of different solutions, from Best, average and worst case.