By

Today’s LeetCode daily challenge requires finding a dominant item that appears more than half the time in an array.
I used a hash map to count each item and track the most frequent one during this process.
This results in O(N*log N) time complexity and O(N) space complexity.
After I applied my solution, I found that most other solutions were much faster than mine.
They all used a simple algorithm to find the dominant item - Boyer-Moore Majority Vote Algorithm:

def majority_element(nums):
    candidate, count = None, 0

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

nums = [3, 3, 4, 2, 3, 3, 3, 1]
print(majority_element(nums))  # Output: 3

If you know that there is a dominant item appears more than half the time in an array, this algorithm will find it in O(N) time and O(1) space.

Amazing!

Contents