How do you solve Majority Element on LeetCode?

Majority Element (LeetCode #169) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The majority element appears more than half the time, which allows us to use counting techniques.

What is the brute force solution for Majority Element?

The brute force approach for Majority Element is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each element in the array and counts how many times it appears. If it appears more than n/2 times, it's the majority element. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Majority Element?

Always clarify assumptions, like the existence of a majority element. Discuss the time and space complexity of your approach. Be prepared to explain your thought process and any trade-offs in your solution.

What are common mistakes when solving Majority Element?

Relying on sorting, which is unnecessary and less efficient. Not considering edge cases like arrays of size 1.

#169

Majority Element

Easy

ArrayHash TableDivide and ConquerSortingCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the Boyer-Moore Voting Algorithm, which efficiently finds the majority element in linear time and constant space by maintaining a candidate and a count.

⚙️

Algorithm

3 steps

1Step 1: Initialize a candidate variable and a count variable.
2Step 2: Iterate through the array, updating the candidate and count based on the current element.
3Step 3: Return the candidate as the majority element.

solution.py8 lines

1def majorityElement(nums):
2    count = 0
3    candidate = None
4    for num in nums:
5        if count == 0:
6            candidate = num
7        count += (1 if num == candidate else -1)
8    return candidate

ℹ

Complexity note: This complexity is achieved because we only make a single pass through the array, and we use constant space for the count and candidate variables.

1The majority element appears more than half the time, which allows us to use counting techniques.
2The Boyer-Moore Voting Algorithm is a powerful method for finding majority elements efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.