Majority Element (Leetcode 169)

Problem Link: https://leetcode.com/problems/majority-element/

Hashing Approach (Time: O(N) and Space: O(N))

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        n=len(nums)
        d={}
        for i in nums:
            if(i not in d):
                d[i]=1
            else:
                d[i]+=1
        
        for i in d:
            if(d[i]>n//2):
                return i

Moore's Voting Algorithm (Time: O(N) and Space: O(1))

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        
        n=len(nums)
        c=0
        ele=-1
        for i in range(n):
            if(c==0):
                ele=nums[i]
            if(nums[i]==ele):
                c+=1
            else:
                c-=1
        return ele

Last updated