169. Majority Element - Explanation

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 in the array. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [5,5,1,1,1,5,5]

Output: 5

Example 2:

Input: nums = [2,2,2]

Output: 2

Constraints:

1 <= nums.length <= 50,000
-1,000,000,000 <= nums[i] <= 1,000,000,000

Follow-up: Could you solve the problem in linear time and in O(1) space?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The majority element appears more than n/2 times. For each element, we can count how many times it appears in the array. If the count exceeds n/2, we've found our answer. This straightforward approach checks every element against every other element.

Algorithm

For each element num in the array:
- Count how many times num appears in the entire array.
- If the count exceeds n / 2, return num.
A majority element is guaranteed to exist, so we will always find one.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        for num in nums:
            count = sum(1 for i in nums if i == num)
            if count > n // 2:
                return num

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Hash Map

Intuition

We can avoid repeated counting by using a hash map to store the frequency of each element as we iterate through the array. We track the element with the maximum count seen so far. Once any element's count exceeds n/2, it must be the majority element.

Algorithm

Create a hash map to store element frequencies.
Initialize res and maxCount to track the current best candidate.
For each element num:
- Increment its count in the hash map.
- If its count exceeds maxCount, update res = num and maxCount = count[num].
Return res.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = defaultdict(int)
        res = maxCount = 0

        for num in nums:
            count[num] += 1
            if maxCount < count[num]:
                res = num
                maxCount = count[num]
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sorting

Intuition

If we sort the array, the majority element must occupy the middle position. Since it appears more than n/2 times, no matter where the majority element's block starts, it will always include the index n/2. This gives us a simple one-liner solution after sorting.

Algorithm

Sort the array.
Return the element at index n / 2.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Bit Manipulation

Intuition

We can construct the majority element bit by bit. For each bit position, we count how many numbers have that bit set. If more than n/2 numbers have the bit set, then the majority element must also have that bit set. We build the result by combining all the majority bits.

Algorithm

Create an array to count set bits at each of the 32 positions.
For each number, add 1 to bit[i] if the i-th bit is set.
For each bit position, if bit[i] > n / 2, set that bit in the result.
Handle the sign bit (bit 31) specially for negative numbers.
Return the constructed result.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        bit = [0] * 32
        for num in nums:
            for i in range(32):
                bit[i] += ((num >> i) & 1)

        res = 0
        for i in range(32):
            if bit[i] > (n // 2):
                if i == 31:
                    res -= (1 << i)
                else:
                    res |= (1 << i)
        return res

Time & Space Complexity

Time complexity: $O(n * 32)$
Space complexity: $O(32)$

$32$ represents the number of bits as the given numbers are integers.

5. Boyer-Moore Voting Algorithm

Intuition

The Boyer-Moore algorithm works by maintaining a candidate and a count. When we see the candidate, we increment the count; otherwise, we decrement it. When the count reaches 0, we pick a new candidate. Since the majority element appears more than half the time, it will survive this elimination process and remain as the final candidate.

Algorithm

Initialize res as the candidate and count = 0.
For each element num:
- If count == 0, set res = num.
- If num == res, increment count; otherwise decrement count.
Return res as the majority element.

class Solution:
    def majorityElement(self, nums):
        res = count = 0

        for num in nums:
            if count == 0:
                res = num
            count += (1 if num == res else -1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

6. Randomization

Intuition

Since the majority element appears more than n/2 times, any random pick has greater than 50% chance of selecting it. We repeatedly pick a random element and check if it's the majority. On average, we need only about 2 picks to find the answer, making this surprisingly efficient in practice.

Algorithm

Randomly select an element from the array.
Count how many times it appears.
If the count exceeds n / 2, return it.
Otherwise, repeat from step 1.

class Solution:
    def majorityElement(self, nums):
        n = len(nums)
        while True:
            candidate = random.choice(nums)
            if nums.count(candidate) > n // 2:
                return candidate

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

The probability of randomly choosing the majority element is greater than $50\%$ , so the expected number of iterations in the outer while loop is constant.

Common Pitfalls

Using >= Instead of > for the Majority Check

The majority element must appear more than n/2 times, not n/2 or more. Using count >= n/2 instead of count > n/2 can return incorrect results for arrays like [1, 2, 2] where 2 appears exactly n/2 times but is not a strict majority.

Forgetting Integer Division Semantics

In languages like Python 3, / performs floating-point division while // performs integer division. Using n / 2 instead of n // 2 can lead to type errors or incorrect comparisons. Similarly, in JavaScript, Math.floor(n / 2) is needed for proper integer division.