Leetcode: Majority Element

Majority Element | LeetCode OJ

We need to find the element whose count is more than half the number of elements in given array

1. Create a dictionary to keep count of each number in the array
2. Traverse the array and update counters
3. Exit as soon as counter of a number exceeds half of length

Remarks:

1. O(n) time complexity as we are traversing the array
2. O(1) space complexity as only constant number of variables are used

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = {}
        l = len(nums) / 2
        for n in nums:
            dp[n] = dp[n] + 1 if n in dp else 1
            if dp[n] > l:
                return n