169_Majority_Element.md

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore majority vote algorithm

Learn More about -> Majority vote algorithm

169. LeetCode

Approach 1

Used a hash-map(python-dictionary) to store the count of elements.
Return the element whose count is greater then length_nums//2

class Solution:
    def majorityElement2(self, nums):
        m = {}
        for n in nums:
            m[n] = m.get(n, 0) + 1
            if m[n] > len(nums)//2:
                return n

Approach 2

Used a variable - res to store the element if count==0.
Increment count if the same value is seen else decrement.

If count reaches zero again we assign the next element to res.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res, count = 0, 0
        for i in nums:
            if count==0:
                res = i
            count += (1 if i==res else -1)
        return res

For certain edge case's where majority element is not present

For example:
list = [ 1,2,2,1,1,2]

We find the majority element using Boyer-Moore majority vote algorithm in a separate funtion
And check if it is greater that length_nums//2 by looping thorugh the array nums.

class Solution:
    def majorityElement(self, A, N):
        '''
        A = given_array 
        N = len(A)
        '''
        #Your code here
        def maj(A):
            res, count = 0,0
        
            for n in A:
                if count == 0:
                    res = n
                count += (1 if n==res else -1)
            return res
        r = maj(A)
        c=0
        for i in A:
            if i ==r:
                c += 1
        if c > N//2:
            return r
        else:
            return -1

Please refer to the aforementioned articles on Majority Vote Algorithm to have a better understanding.