#169

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Majority Element

Find the majority element in an array, where the element appears more than n/2 times, using efficient algorithms.

array hash table divide and conquer sorting counting

Problem Statement

Given an integer array nums of size n, you need to find the majority element. The majority element is defined as the element that appears more than ⌊n / 2⌋ times in the array.

You can assume that the majority element always exists in the array. For instance, given the input nums = [3, 2, 3], the output would be 3, as 3 appears more than half the time.

Examples

Example 1

Input: nums = [3,2,3]

Output: 3

Example details omitted.

Example 2

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

Output: 2

Example details omitted.

Constraints

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

Solution Approach

Hash Table Approach

A straightforward solution involves using a hash table to count occurrences of each element. Traverse the array and update the count for each element. Once an element's count exceeds n / 2, return it as the majority element.

Sorting Approach

By sorting the array, the majority element will always appear in the middle. This method has a time complexity of O(n log n), as the sorting step is the most time-consuming operation.

Boyer-Moore Voting Algorithm

This optimal algorithm reduces the problem to O(n) time and O(1) space. It maintains a count and candidate element while scanning the array. If the count is 0, switch the candidate; otherwise, increment or decrement the count based on the current element.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The hash table approach requires O(n) time and O(n) space. Sorting the array has a time complexity of O(n log n) and O(1) space. The Boyer-Moore Voting Algorithm is the most efficient with O(n) time and O(1) space, making it the best solution for larger arrays.

What Interviewers Usually Probe

Test the candidate's ability to implement the Boyer-Moore Voting Algorithm, which is an optimal solution for this problem.
Look for understanding of time and space complexity, particularly when discussing the hash table or sorting approaches.
Evaluate the candidate's problem-solving flexibility by asking about the trade-offs between different approaches.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the definition of majority element and thinking that the most frequent element is the majority.
Overcomplicating the solution with unnecessary extra space or sorting when simpler methods like the Boyer-Moore Voting Algorithm exist.
Forgetting that the problem guarantees the existence of a majority element, leading to unnecessary checks.

Follow-up variants

Find the majority element in a stream of data where you can only access one element at a time.
Extend the problem to find the majority element in multiple arrays combined.
Modify the problem to work with an array where elements appear more than once but less than half the time.

FAQ

What is the time complexity of the Majority Element problem?

The time complexity depends on the approach used. The hash table approach is O(n), sorting is O(n log n), and the Boyer-Moore Voting Algorithm is O(n).

How do I solve Majority Element using Boyer-Moore Voting Algorithm?

The Boyer-Moore Voting Algorithm involves scanning the array while maintaining a count and a candidate element. When the count becomes 0, switch the candidate. This method has O(n) time complexity and O(1) space complexity.

Can the Majority Element problem be solved using sorting?

Yes, by sorting the array, the majority element will always appear in the middle of the array. This method has a time complexity of O(n log n).

What is the optimal space complexity for Majority Element?

The optimal space complexity is O(1), achieved by using the Boyer-Moore Voting Algorithm.

What is the Majority Element problem pattern?

The Majority Element problem involves scanning the array and using hash lookups or specialized algorithms like Boyer-Moore to find the element that appears more than n/2 times.

terminal

Solution

Solution 1: Moore Voting Algorithm

The basic steps of the Moore voting algorithm are as follows:

1

2

3

4

5

6

7

8

9

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = m = 0
        for x in nums:
            if cnt == 0:
                m, cnt = x, 1
            else:
                cnt += 1 if m == x else -1
        return m

Continue Practicing

#347 top k frequent elements #229 majority element ii #594 longest harmonious subsequence