Problem statement

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

Solution

Simple problem, but it is good to investigate — it has a lot of different solutions. There is a simple hashtable solution with time and memory complexity O(n), there is a sorting solution with O(n * log n) time and O(1) memory.

Remember, that we did not use the fact, that majority element is in more than half place. Finally there is Boyer-Moore Voting Algorithm, with time complexity O(n) and space complexity O(1): the idea is to keep track of current most popular element and if new element is equal to the most popular, we add 1, if not equal, we subtract -1. If we have zero, we forget about all previous elements and update current most popular.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def majorityElement(self, nums):
        cnt, cand = 0, None
        
        for num in nums:
            if cnt == 0: cand = num
            cnt += (1 if num == cand else -1)
            
        return cand

Remark

Also there is randomization solution with expected linear time and constant memory.