Majority Element II LeetCode solution in Python

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> List[int]:
3

4
        # Boyer Moore Voting Algo (As used in ME1 ques)
5
        # now we can observe that there cannot be more than two elements occuring more than n//3 times in an array
6
        # so find two majority elements(me=majority element)
7

8
        n = len(nums)
9
        req = n // 3  # for an element to be ME required number of times present
10

11
        c1 = 0  # count 1
12
        c2 = 0  # count 2
13
        me1 = None  # majority element 1
14
        me2 = None  # majority element 2
15

16
        for i in nums:
17
            if i == me1:
18
                c1 += 1
19

20
            elif i == me2:
21
                c2 += 1
22

23
            elif c1 == 0:
24
                me1 = i
25
                c1 = 1
26

27
            elif c2 == 0:
28
                me2 = i
29
                c2 = 1
30

31
            else:
32
                c1 -= 1
33
                c2 -= 1
34
        # here we have found our majority elements now check if the found majority element is ME
35
        # print(me1,me2)
36

37
        # check if the found majority element is ME
38
        c1 = 0
39
        c2 = 0
40
        for i in nums:
41
            if i == me1:
42
                c1 += 1
43
            if i == me2:
44
                c2 += 1
45
        # print(c1,c2)
46

47
        if c1 > req and c2 > req:
48

49
            return [me1, me2]
50

51
        elif c1 > req:
52
            return [me1]
53

54
        elif c2 > req:
55
            return [me2]