Majority Element

Problem Description

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.

Examples

Constraints

• n == nums.length
• 1 <= n <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

Tracking Majority by Canceling Candidates

While counting frequencies with a hash map requires O(n) space, you can find the majority element in O(1) space by treating elements as votes. The Boyer-Moore Voting Algorithm maintains a candidate and a counter. If the current element matches the candidate, increment the count; otherwise, decrement it. If the count reaches 0, establish the current element as the new candidate. Because the majority element appears more than ⌊n / 2⌋ times, it will survive the cancellations.

Solution 1: Boyer-Moore Voting Algorithm

Scan the array while balancing a candidate’s vote frequency.

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

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

#include <vector>

class Solution {
public:
    int majorityElement(std::vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the array once.
• Space Complexity: O(1) auxiliary space as we only use primitive tracking variables.

Where It Breaks

This algorithm relies on the assumption that a majority element always exists. If no element occurs more than ⌊n / 2⌋ times, Boyer-Moore will still return a candidate, but it may not be the true majority element. A second verification pass is required if the existence of the majority element is not guaranteed.

Common Mistakes

• Incorrect reset condition: Resetting the candidate before the count drops to zero.
• Ignoring negative values: Assuming elements are positive or small numbers and using an array-based counter that triggers index out of bounds.

Frequently Asked Questions

Can we sort the array? Yes. If you sort the array, the majority element will always be located at the middle index ⌊n / 2⌋. Sorting takes O(n log n) time and O(1) to O(n) space, which is less efficient than linear time Boyer-Moore.

Why does Boyer-Moore work? Because the majority element appears more than half the time, even if all other elements “vote against” the majority element, they do not have enough combined occurrences to cancel out the majority element’s votes.

← All Problems