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