# Simple O(n) time O(1) space complete solution

• The observation is that a majority element in the whole list has to be a local majority element in some sublist.

On the other hand, it is possible that a local majority element does not necessarily be the majority element in the whole list, as some list may not have a majority element, e.g., 1, 1, 1, 2, 2, 3, 3, 3. Thus we need to validate the candidate in the end to make sure it is indeed a majority element of the whole list.

``````class Solution(object):
def getCandidate(self, nums):
count = 0
for num in nums:
if count is 0:
candidate = num
if candidate == num:
count += 1
else:
count -= 1
return candidate

def validateCandidate(self, nums, candidate):
count = 0
for num in nums:
if num == candidate:
count += 1
return candidate if count > len(nums) / 2 else -1

def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
candidate = self.getCandidate(nums)
return self.validateCandidate(nums, candidate)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.