Given an array nums of size n, return the majority element. 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.

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Examples:

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Solution

Problem Insight

The core property of the majority element is that it appears strictly more than n / 2 times. This means its count is greater than the combined count of all other elements in the array.

Approach: Boyer-Moore Voting Algorithm

This algorithm is an efficient way to find the majority element with optimal time and space complexity.

  • Initialization: Maintain two variables: count (initialized to 0) and majority_candidate (initialized to an arbitrary value, or the first element, or None if handling first element specially).
  • Iteration: Iterate through each num in the input array nums:
    • If count becomes 0, it means the previous majority_candidate has been 'outvoted' or we're starting fresh. In this case, set majority_candidate to the current num.
    • If the current num is equal to majority_candidate, increment count.
    • Otherwise (if num is different from majority_candidate), decrement count.
  • Result: After iterating through the entire array, majority_candidate will hold the majority element.

Why it Works

The algorithm cleverly leverages the majority property. Every time a non-majority element is encountered, it 'cancels out' one instance of the current majority_candidate. Since the true majority element appears more than n/2 times, it will always 'outvote' all other elements, ensuring it remains the majority_candidate with a positive count at the end.

Complexity Analysis

  • Time Complexity: O(n) because we perform a single pass through the array.
  • Space Complexity: O(1) as we only use a few constant extra variables.

Python Code Solution

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        count = 0
        majority_candidate = 0 # This will be overwritten if count starts at 0

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