How do you solve Majority Element II on LeetCode?

Majority Element II (LeetCode #229) 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: There can be at most two elements that appear more than n/3 times due to the pigeonhole principle.

What is the brute force solution for Majority Element II?

The brute force approach for Majority Element II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each element and counts its occurrences in the array. If the count exceeds n/3, we add it to the result list. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Majority Element II?

Majority Element II uses the following concepts: Array, Hash Table, Sorting, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Majority Element II?

Always clarify the constraints and edge cases before diving into coding. Explain your thought process while coding; it helps the interviewer follow your logic. Practice dry-running your code with sample inputs to catch potential mistakes.

What are common mistakes when solving Majority Element II?

Failing to consider that there can be at most two majority elements. Not resetting counts properly when switching candidates in the optimal solution.

#229

Majority Element II

Medium

ArrayHash TableSortingCountingHash 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)

Using the Boyer-Moore Voting Algorithm, we can find candidates for majority elements efficiently. Since there can be at most two elements that appear more than n/3 times, we can track two candidates and their counts.

⚙️

Algorithm

4 steps

1Step 1: Initialize two candidates and their counts to zero.
2Step 2: Iterate through the array to find the two potential candidates.
3Step 3: Reset counts and verify the candidates by counting their occurrences.
4Step 4: If their counts exceed n/3, add them to the result.

solution.py23 lines

1# Full working Python code
2
3def majorityElement(nums):
4    if not nums:
5        return []
6    count1, count2, candidate1, candidate2 = 0, 0, None, None
7    for num in nums:
8        if num == candidate1:
9            count1 += 1
10        elif num == candidate2:
11            count2 += 1
12        elif count1 == 0:
13            candidate1, count1 = num, 1
14        elif count2 == 0:
15            candidate2, count2 = num, 1
16        else:
17            count1 -= 1
18            count2 -= 1
19    result = []
20    for candidate in (candidate1, candidate2):
21        if nums.count(candidate) > len(nums) // 3:
22            result.append(candidate)
23    return result

ℹ

Complexity note: The time complexity is O(n) because we make a single pass to find candidates and another pass to count their occurrences. The space complexity is O(1) since we only use a fixed amount of extra space.

1There can be at most two elements that appear more than n/3 times due to the pigeonhole principle.
2Using a counting strategy allows us to efficiently track potential majority candidates.

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