# Majority Element II

Description

Given an array of integers, the majority number is the number that occurs `more than 1/3`

of the size of the array.

There is only one majority number in the array.

**Example 1:**

Input:

`nums = [99,2,99,2,99,3,3]`

Output:

`99`

Explanation:

99 appeared three times.

**Example 2:**

Input:

`nums = [1, 2, 1, 2, 1, 3, 3]`

Output:

`1`

Approach 1:

Naive approach

Similar to finding the majority element with the occurence greater than n/2, this problem also can be done in O(n²) time complexity. We iterate through the array using an outer loop and then, by inner loop , again iterate through the array to find the count of current element.

Time: O(n²)

Space: O(1)

Approach 2:

Using a hash table

We iterate through the array and keep count of each distinct numbers in the table. Then the number with a count greater than n/3 is chosen.

Time :O(n)

Space :O(n)

Approach 3:

Moore voting algorithm.

For finding the majority element having occurence greater than n/3 , one point to note is , we can’t have more than 2 such majority element in the array. So we essentially find two of such possible candidates which can be the major element using Moore voting. Then we check , which of these 2 candidates has occurence >n/3 , by one more iteration over the array.

Time: O(n)

Space: O(1)

Thus this is much more optimised solution, in terms of space and time.

Additional Question

What if the frequency of majority element is taken as n/k , where k can be any variable

Approach 1:

For loops, hashing can be used here. But let’s see more optimized solution in terms of space and time , using Moore algorithm.

Hint: The maximum possible majority elements in that case will be k-1

Therefore we take a hash table to store those k-1 candidates while using the Moore voting algorithm. All other steps are same as done for above problem(n/3)

Solution:

def majorityNumber(self, nums): candidate1=None candidate2=None vote1=0 vote2=0 one_3=len(nums)//3 for i in nums: if(candidate1==i): vote1+=1 elif(candidate2==i): vote2+=1 elif(vote1==0): candidate1=i vote1=1 elif(vote2==0): candidate2=i vote2=1 else: vote1-=1 vote2-=1 #end of for count_of_cand1=0 count_of_cand2=0 for i in nums: if(i==candidate1): count_of_cand1+=1 elif(i==candidate2): count_of_cand2+=1 print(candidate1,candidate2) return [candidate1,candidate2][count_of_cand2>one_3]

Time : O(n)

Space: O(k-1)