Majority Element

+10

You get an array of integers nums of length n. One value appears in it more than n / 2 times, and that value is called the majority element. Return it. A value that fills more than half the array is always unique, so there is exactly one answer.

Function

majorityElement(nums: integer-array) → integer

numsinteger-array: the array of integers, with one value filling more than half of it
Returnsinteger: the value that appears more than n / 2 times

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
One value appears more than nums.length / 2 times.

Examples

Input: nums = [3, 9, 3, 3, 4]
Output: 3
Explanation: 3 appears three times in five elements. Three is more than 5 / 2 = 2.5, and 9 and 4 appear once each.

+15 hidden tests on Submit

Follow-up

Can you find the majority element in O(n) time with O(1) extra memory, without sorting the array?

Solution

Counting how often each value appears answers the question, but the counts need a hash map. The way to drop it is to see what makes the majority special: it outnumbers all the other values put together. Pair each copy of it with a different value and cross both out, and some copies are always left. Boyer-Moore voting does that pairing in one pass with one candidate and one counter.

Count with a hash map

Intuition

Walk through the array and keep a hash map from each value to the number of times you have seen it. After you add one to a value's count, check whether that count is now more than half the length. The first value to cross that line is the majority, so you can return it at once.

For [3, 9, 3, 3, 4], the count of 3 becomes 1 at index 0, 2 at index 2 and 3 at index 3. Three copies out of five is more than 2.5, so you return 3 without reading the last element.

A hash map lookup and update take O(1) on average, so the time is O(n). The map can hold up to about n / 2 different values, so the extra memory is O(n). The next approach gets rid of the map.

Algorithm

Create an empty map from value to count.
For each element x, add 1 to the count of x.
If that count times 2 is greater than the length of the array, return x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Boyer-Moore voting

Intuition

Treat the array as an election. Keep one candidate and a count of its votes that nothing has cancelled yet. An element equal to the candidate adds a vote. An element that differs cancels one vote, and the two leave the race together. When the count is 0, the next element becomes the new candidate.

Why the value left at the end is the majority: every cancellation removes two different values, so it removes at most one copy of the majority. Say the majority appears m times. There are only n - m other elements, fewer than m, so they cannot cancel every copy. Every vote still standing at the end belongs to the final candidate, and a copy of the majority is among them, so the candidate is the majority.

On [8, 8, 1, 1, 8, 1, 8] the count goes 1, 2, 1, 0: the two 1s have cancelled both 8s. The next 8 starts over with a count of 1, the next 1 cancels it, and the last 8 becomes the candidate again. You return 8. One pass with two variables gives O(n) time and O(1) memory.

Algorithm

Set candidate to the first element and count to 0.
For each element x, if count is 0, make x the candidate.
If x equals the candidate, add 1 to count. Otherwise subtract 1.
After the last element, return candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Pitfalls and edge cases

Most wrong answers come from the halfway line or from reading too much into the counter.

"More than half" is strict. count >= n / 2 accepts 2 copies out of 4, which is not a majority. Compare count * 2 > n and no rounding can get in the way.
The final count in Boyer-Moore is not how often the majority appears. For [8, 8, 1, 1, 8, 1, 8] it ends at 1, while 8 appears four times.
Starting with candidate = nums[0] and count = 1 works only if the loop then starts at index 1. Start it at index 0 and the first element votes twice: on [1, 2, 2] the count ends at 0 and you return 1.
Boyer-Moore relies on the guarantee. On [1, 2, 3], which has no majority, it still returns 3. If an input might lack a majority, count the candidate in a second pass before you trust it.

Frequently asked questions4

What is the Boyer-Moore voting algorithm?

It finds the value that fills more than half of a list in one pass with O(1) memory. It keeps a candidate and a counter: a matching element adds one, a different element subtracts one, and at 0 the next element becomes the candidate. Because the majority outnumbers every other value combined, it is the candidate left at the end.

What is the time and space complexity of Majority Element?

Boyer-Moore voting runs in O(n) time and O(1) extra space. Counting with a hash map is also O(n) time but needs O(n) space for the counts. Sorting first takes O(n log n) time.

Can Majority Element be solved by sorting?

Yes. After sorting, all copies of the majority sit in one block longer than half the array, and any such block covers the middle position. So the element at index n / 2, rounded down, is the answer. It is short to write but costs O(n log n) time.

What if the array might not have a majority element?

Boyer-Moore always returns some candidate, even when no value fills more than half the array. Add a second pass that counts the candidate and accept it only if the count is more than n / 2. The total stays O(n) time and O(1) space.

Python

def majorityElement(nums):
    # Write code here

Test cases

Case 1

Case 2

Input

nums = [3, 9, 3, 3, 4]

Expected