Majority Element II
Majority Element II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.
Problem statement
Implement the Solution class and its majorityElement method. The parameter nums is an array of integers, and n is the number of elements in nums.
A value is a qualifying majority value if its frequency in nums is greater than floor(n/3), where floor means rounding down to the greatest integer no larger than its argument. Count occurrences by value, regardless of their positions in the array.
Return a list containing every qualifying value and no other values. The returned values may appear in any order. If no value qualifies, return an empty list.
Example 1:
Input: nums = [4,4,7,4,7,7,7,2] Output: [4,7] Explanation: There are 8 elements, so a value must appear more than floor(8/3) = 2 times. The values 4 and 7 appear 3 and 4 times, respectively.
Example 2:
Input: nums = [1,2,3,2,3,4] Output: [] Explanation: With 6 elements, a value must appear more than 2 times. Both 2 and 3 appear exactly twice, so no value qualifies.
Example 3:
Input: nums = [-8] Output: [-8] Explanation: For one element, the threshold is floor(1/3) = 0, so the only value appears often enough to qualify.
Constraints:
- 1 <= nums.length <= 10^5 - nums contains only integers - The result contains every value whose frequency is greater than floor(nums.length / 3) - The result contains no duplicate values
Topics and companies
Topics: Array, Counting, Iteration.
How to practise Majority Element II on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Majority Element II in the code editor, or read the Majority Element II editorial for a worked solution with its approach and complexity analysis.
Where Majority Element II sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Hashing - Frequency Map / Counting subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Majority Element II
Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:
- Find the Town Judge — Easy, same subpattern
- Group Anagrams — Medium, same subpattern
- Majority Element — Easy, same subpattern
- Subarray Sum Equals K — Medium, same subpattern
- Two Sum — Easy, same subpattern
- Valid Anagram — Easy, same subpattern