Majority Element Ii - Leetcode Solution

The problem "Majority Element II" on LeetCode asks us to find all the elements that appear more than ⌊n/3⌋ times in an array of integers.

Approach:

We need to find all the elements appearing more than ⌊n/3⌋ times in an array. For that, we need to keep track of all the elements that have an occurrence of more than ⌊n/3⌋. We cannot solve this problem using the same Boyer-Moore algorithm used in the problem "Majority Element I". The reason for that is, here we need to keep track of two variables instead of one, and this algorithm only works for finding one majority element.

We can use the "Boyer-Moore" algorithm with a slight modification that we keep track of two candidates instead of one. We initialize two variables 'candidate1' and 'candidate2' as 'None' and their count as 0. Then, we traverse the array and update our two candidates and count based on the following rules:

Rule1:

If the current element is equal to 'candidate1', we increment its count.

Rule2:

If the current element is equal to 'candidate2', we increment its count.

Rule3:

If one of the candidates has zero occurrences, we update the candidate with the current element.

Rule4:

If neither candidate has zero occurrences and the current element is not equal to any of them, we decrement their respective counts.

Finally, we traverse the array again to find the occurrence of these two candidates. Any candidate with an occurrence greater than ⌊n/3⌋ is our required element. If none of the candidates satisfy this condition, we return an empty list.

Code:

Here is the implementation of the above algorithm in Python:

def majorityElement(nums): candidate1, candidate2 = None, None count1, count2 = 0, 0

for num in nums:
    if num == candidate1:
        count1 += 1
    elif num == candidate2:
        count2 += 1
    elif count1 == 0:
        candidate1, count1 = num, 1
    elif count2 == 0:
        candidate2, count2 = num, 1
    else:
        count1 -= 1
        count2 -= 1

count1, count2 = 0, 0
for num in nums:
    if num == candidate1:
        count1 += 1
    elif num == candidate2:
        count2 += 1

res = []
if count1 > len(nums)//3:
    res.append(candidate1)
if count2 > len(nums)//3:
    res.append(candidate2)
    
return res

This code has time complexity O(n) and space complexity O(1).

Testing:

We can test the above implementation with the following test cases:

assert majorityElement([3,2,3]) == [3] assert majorityElement([1,1,1,3,3,2,2,2]) == [1,2] assert majorityElement([1,1,1,1]) == [1] assert majorityElement([1,2,3,4]) == []

All these test cases passed successfully.

1