Problem Statement in English

You’re given an array nums of size n. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the majority element always exists in the array.

Approach

In order to do this in $O(n)$ time and $O(1)$ space, we can use the Boyer-Moore Voting Algorithm.

The idea is to maintain a candidate for the majority element and a count. We iterate through the array, and for each element, we either increment the count if it matches the candidate or decrement it if it doesn’t. If the count reaches zero, we select a new candidate. By the end of the iteration, the candidate will be the majority element.

This is guaranteed to work because the majority element appears more than half the time, so it will always be the last candidate standing.

And we’re done!

Solution in Python


class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None
        count = 0
        
        for num in nums:
            if count == 0:
                candidate = num
            
            if num == candidate:
                count += 1
            else:
                count -= 1
                
        return candidate

Complexity

  • Time: $O(n)$
    Since we are iterating through the list of numbers once, the time complexity is linear with respect to the number of elements in the input list.

  • Space: $O(1)$
    Since we are using a constant amount of extra space (for the candidate and count variables), the space complexity is constant.

Mistakes I Made

I had to look up the Boyer-Moore Voting Algorithm to understand how to find the majority element efficiently. Initially, I was trying to use a hash map to count occurrences, which would have increased space complexity.

And we are done.