Majority Element (Leetcode 169)

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

Note: There are many other ways using sorting, hashing etc. But, the below method takes O(N) time and O(1) space. So, this is the best way. We simply cancel out the the element which occurred most no of times so far as we traverse.

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