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)