Majority Element

Repeating Number

Problem

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:

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

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

Thought Process

• Moore's Voting Algorithm: Moore's Voting Algorithm is an algorithm for finding the majority in a sequence of elements using linear time and constant space.

• For this problem, we will:

  • 1) Find the candidate with $count > 0$ (this is where we use Moore's to find a potential candidate for majority element)

    • However, just because its the candidate does not mean it occurs more than $n/2$ times. This is why we have to verify it

  • 2) Iterate back through the array to verify this candidate appears more than $n/2$ times.

Solution

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        verify = len(nums)//2
        major = nums[0]
        count = 1
        
        for i in range(1,len(nums)):
            if nums[i] == major:
                count+=1
            elif(nums[i]!=major):
                count-=1
            if count == 0:
                count = 1
                major = nums[i]
        count2 = 0
        for i in range(len(nums)):
            if nums[i] == major:
                count2+=1
        if count2 > verify:
            return major

Key Facts

• Moore's Voting Algorithm is important for this problem as it helps us potentially find the majority element. We then have to verify if this element is in fact the majority element

• We intially have to set the first element as the majority element to start.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$