Majority Element

Patrick Leaton
Published: April 14, 2021, 12:19 a.m.
Problem Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

 

 

Description taken from https://leetcode.com/problems/majority-element/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1
        return candidate

Problem Explanation

A couple of good approaches that may come to mind are to sort the array and return the middle element, or to make a HashMap that keeps count of occurrences for each value in the array.

The optimal approach is the Boyer-Moore Voting Algorithm.

This algorithm uses a counter and a candidacy value when traversing the list to consider elements as the majority element, each time the candidate is seen again then its count is incremented.  If another value is seen then its count is decremented.

By the time the entire array is scanned, the candidate value will be the majority element.

Let's start by setting the first candidate to none and its initial count to zero.

        count = 0
        candidate = None

 

We will start by traversing the input array.

The initial candidate will be the first element of the array since the counter is starting at zero.

        for num in nums:
            if count == 0:
                candidate = num

 

During each iteration, if the current element's value is the same as the current candidate's value, we will increment the counter.

            if num == candidate:
                count += 1

 

Otherwise, we will decrement the counter. 

            else:
                count -= 1

 

If the counter gets set back to zero in a future iteration, then we will trash the current candidacy and make that iteration's current element the new candidate.  

The overall idea is that we will trash more candidacies of the wrong value than candidacies of the right value by the time we have traversed the entire array.  

We can return this final candidate's value.

        return candidate