Majority Element

Q: What if the array might not have a majority element?

Boyer-Moore always returns some candidate: on [1, 2, 3] it returns 3. 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.

EasyHashing

+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.

Follow-up

Can you find every value that appears more than n / 3 times, in O(n) time with O(1) extra memory?

Solution

The majority outnumbers all the other values put together. Cross out pairs of different values and some of its copies always survive. Boyer-Moore voting does that pairing in one pass with one candidate and one counter, so you need no hash map of counts.

Count with a hash map

Intuition

Count each value in a hash map and return the first value whose count passes half the length. For [3, 9, 3, 3, 4], the count of 3 reaches 3 at index 3, more than 2.5, so you return before reading the 4.

Each lookup is O(1) on average, so the time is O(n), but the map can hold about n / 2 different values: O(n) memory.

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

Keep a candidate and a count of its votes not yet cancelled. An element equal to the candidate adds a vote. A different one cancels a vote, and both leave the race. At count 0, the next element becomes the candidate.

Each cancellation removes two different values, so at most one copy of the majority. If the majority appears m times, the other n - m elements number fewer than m and cannot cancel every copy. Every vote standing at the end belongs to the final candidate, and a copy of the majority is among them.

On [8, 8, 1, 1, 8, 1, 8] the count goes 1, 2, 1, 0 as the 1s cancel both 8s. The next 8 restarts at 1, the next 1 cancels it, and the last 8 becomes the candidate again. 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

"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 gets in the way.
Reading the final count as the majority's frequency. 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, then looping from index 0. The first element votes twice: on [1, 2, 2] the count ends at 0 and you return 1.

Frequently asked questions3

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, at a cost of O(n log n) time.

What if the array might not have a majority element?

Boyer-Moore always returns some candidate: on [1, 2, 3] it returns 3. 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.

def majorityElement(nums):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output