Majority Element
Majority Element is a Easy 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 Solution.majorityElement(nums), where nums is a non-empty array of integers. Let n be the number of elements in nums; an integer is a majority element when it occurs more than n / 2 times in the array.
A majority element is guaranteed to exist. Return that integer. The order of the elements in nums is otherwise unrestricted, and the returned value must be the element itself rather than its frequency.
Example 1:
Input: nums = [4,4,2,4,3,4,4] Output: 4 Explanation: The value 4 occurs five times out of seven positions, which is more than half.
Example 2:
Input: nums = [-3,1,-3,2,-3,-3] Output: -3 Explanation: The value -3 appears four times out of six positions, so it is the guaranteed majority.
Example 3:
Input: nums = [7] Output: 7 Explanation: The only element appears once, which is more than half of the one-element array.
Constraints:
- 1 <= nums.length <= 10^5 - nums contains only integers - A majority element exists in nums - The majority element appears more than nums.length / 2 times
Topics and companies
Topics: Array, Counting, Greedy, Iteration.
How to practise Majority Element 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 in the code editor, or read the Majority Element editorial for a worked solution with its approach and complexity analysis.
Where Majority Element 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
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 II — Medium, same subpattern
- Subarray Sum Equals K — Medium, same subpattern
- Two Sum — Easy, same subpattern
- Valid Anagram — Easy, same subpattern