LeetCode 169 - Majority Element

LeetCode Problem 169

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Divide and Conquer, Sorting, Counting

Solution

Problem Understanding

The problem asks us to identify the majority element in a given array of integers nums. The majority element is defined as the number that appears more than half of the times in the array, i.e., more than ⌊n / 2⌋ times where n is the length of the array. The input array can contain both positive and negative integers, and the length can range from 1 to 50,000. The problem guarantees that a majority element always exists, which simplifies the solution because we do not have to handle the case where no majority exists.

In other words, we are asked to scan the array and find the element that dominates the array in frequency. The expected output is this element itself. Constraints indicate that the array could be large, so inefficient solutions might not be acceptable. Key edge cases include arrays with a single element, arrays where all elements are the same, and arrays where the majority element is at the beginning, middle, or end.

Approaches

The simplest brute-force method is to count the frequency of each element. We can do this using a hash map (dictionary in Python or map in Go) where the key is the element and the value is its count. After counting, we iterate through the map to find the element whose count exceeds n // 2. While this approach is correct, it requires O(n) space and O(n) time.

A better solution leverages the Boyer-Moore Voting Algorithm, which relies on the observation that the majority element appears more than half the time. By maintaining a candidate and a counter, we can traverse the array once, incrementing the counter when the current element matches the candidate and decrementing it otherwise. If the counter drops to zero, we pick the current element as the new candidate. By the end of the array, the candidate is guaranteed to be the majority element. This approach achieves O(n) time and O(1) space, which meets the follow-up requirement.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Count frequencies using a hash map and find the element exceeding n/2
Optimal (Boyer-Moore)	O(n)	O(1)	Maintain a candidate and counter to identify majority element in one pass

Algorithm Walkthrough

1. Initialize candidate as None and count as 0. This sets up a placeholder for tracking the potential majority element.
2. Iterate over each element num in the array nums.
3. If count is 0, update candidate to the current num. This means we are starting a new potential majority.
4. If num equals candidate, increment count. This reinforces our current candidate.
5. If num does not equal candidate, decrement count. This cancels out a previous occurrence of a different element.
6. After traversing the entire array, return candidate. The algorithm guarantees that candidate is the majority element because the majority element cannot be completely canceled out by other elements.

Why it works: Since the majority element appears more than half the time, every time it encounters a different element, the counter only reduces by one. Because the majority element has more occurrences than all other elements combined, it will remain as the candidate at the end.

Python Solution

from typing import List

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

The implementation initializes the candidate and counter. It iterates through nums, updating the candidate whenever the count drops to zero, and adjusts the counter according to whether the current element matches the candidate. The final candidate is returned as the majority element.

Go Solution

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

The Go implementation mirrors the Python version. We use integer variables candidate and count. The main difference is that Go does not have built-in lists with dynamic resizing like Python, but slices provide the same functionality for iteration. No nil handling is needed because the array is guaranteed to have at least one element.

Worked Examples

Example 1: nums = [3,2,3]

Step	num	candidate	count	Explanation
1	3	None -> 3	0 -> 1	count=0, pick 3 as candidate
2	2	3	1 -> 0	2 != 3, decrement count
3	3	2 -> 3	0 -> 1	count=0, pick 3 as new candidate

Return 3.

Example 2: nums = [2,2,1,1,1,2,2]

Step	num	candidate	count	Explanation
1	2	None -> 2	0 -> 1	pick 2
2	2	2	1 -> 2	match, increment
3	1	2	2 -> 1	mismatch, decrement
4	1	2	1 -> 0	mismatch, decrement, count=0
5	1	1	0 -> 1	pick new candidate 1
6	2	1	1 -> 0	mismatch, decrement, count=0
7	2	2	0 -> 1	pick new candidate 2

Return 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array, constant time per element
Space	O(1)	Only two integer variables are used, no extra data structures

The linear time complexity ensures scalability up to the maximum allowed input size, and constant space meets the follow-up requirement.

Test Cases

# provided examples
assert Solution().majorityElement([3,2,3]) == 3  # simple odd-length array
assert Solution().majorityElement([2,2,1,1,1,2,2]) == 2  # majority at end

# single element
assert Solution().majorityElement([5]) == 5  # edge case, array of length 1

# all elements same
assert Solution().majorityElement([1,1,1,1,1]) == 1  # all identical

# majority at start
assert Solution().majorityElement([9,9,8,8,9]) == 9  # majority at beginning

# majority in middle
assert Solution().majorityElement([4,4,5,4,5,4,6]) == 4  # majority in middle

Test	Why
[3,2,3]	Odd-length, majority in first position
[2,2,1,1,1,2,2]	Majority element at the end, mix of elements
[5]	Single-element edge case
[1,1,1,1,1]	All elements identical
[9,9,8,8,9]	Majority at the start
[4,4,5,4,5,4,6]	Majority in the middle with other elements interspersed

Edge Cases

One important edge case is an array with a single element. The algorithm handles this correctly because the candidate is initialized as None and updated immediately to the single element, which is trivially the majority. Another edge case is an array where all elements are identical. Here, the counter will increment repeatedly without any decrements, resulting in the correct majority. Finally, arrays where the majority element appears at irregular positions, such as at the start, middle, or end, could trip up naive algorithms that stop after finding a local maximum; the Boyer-Moore algorithm correctly aggregates counts across the entire array. In all these cases, the algorithm ensures correctness by maintaining a running candidate and counter invariant.