Majority Element

Difficulty: Easy | Acceptance: 66.30% | Paid: No Topics: Array, Hash Table, Divide and Conquer, Sorting, Counting

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
• Brute Force
• Hash Map
• Sorting
• Divide and Conquer
• Boyer-Moore Voting Algorithm

Examples

Example 1:

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

Example 2:

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

Constraints

- n == nums.length
- 1 <= n <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
- The input is generated such that a majority element will exist in the array.

Brute Force

Intuition Check every element in the array to see if it is the majority element by counting its occurrences.

Steps

• Iterate through each element in the array.
• For each element, count how many times it appears in the array.
• If the count is greater than n/2, return that element.

class Solution:\n    def majorityElement(self, nums: list[int]) -> int:\n        n = len(nums)\n        for num in nums:\n            count = 0\n            for x in nums:\n                if x == num:\n                    count += 1\n            if count > n // 2:\n                return num\n        return -1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays.

Hash Map

Intuition Use a hash map to count the frequency of each element as we iterate through the array.

Steps

• Initialize an empty hash map.
• Iterate through the array, updating the count for each number in the map.
• If any number’s count exceeds n/2, return that number immediately.

class Solution:\n    def majorityElement(self, nums: list[int]) -> int:\n        n = len(nums)\n        counts = {}\n        for num in nums:\n            counts[num] = counts.get(num, 0) + 1\n            if counts[num] > n // 2:\n                return num\n        return -1

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Linear time complexity but requires extra space for the hash map.

Sorting

Intuition If the array is sorted, the majority element will always be at the middle index (n/2) because it occupies more than half of the array space.

Steps

• Sort the array in non-decreasing order.
• Return the element at index n/2.

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

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting implementation.
• Notes: Modifies the original array.

Divide and Conquer

Intuition Recursively find the majority element in the left half and the right half of the array. If they are the same, that is the majority element. If they differ, count their occurrences in the combined array to determine the winner.

Steps

• Base case: if the array has only one element, return that element.
• Recursively find the majority element in the left half and the right half.
• If the two majority elements are equal, return it.
• Otherwise, count the occurrences of both elements in the current scope and return the one with the higher count.

class Solution:\n    def majorityElement(self, nums: list[int]) -> int:\n        def majority_element_rec(lo, hi):\n            if lo == hi:\n                return nums[lo]\n            mid = (hi - lo) // 2 + lo\n            left = majority_element_rec(lo, mid)\n            right = majority_element_rec(mid + 1, hi)\n            if left == right:\n                return left\n            left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)\n            right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)\n            return left if left_count > right_count else right\n        return majority_element_rec(0, len(nums) - 1)

Complexity

• Time: O(n log n)
• Space: O(log n) for the recursion stack.
• Notes: Conceptually elegant but generally slower than linear approaches.

Boyer-Moore Voting Algorithm

Intuition Maintain a candidate and a counter. If the counter is zero, pick the current number as the candidate. If the current number matches the candidate, increment the counter; otherwise, decrement it. The majority element will survive the cancellations.

Steps

• Initialize count to 0 and candidate to null.
• Iterate through the array.
• If count is 0, set candidate to the current number.
• If the current number equals candidate, increment count; otherwise, decrement count.
• Return candidate.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with linear time and constant space.