169. Majority Element
Majority Element (LeetCode 169) 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.
How to solve Majority Element
Majority Element is a Hashing Frequency Map and Counting problem, part of Array/Matrix Manipulation Patterns. Master hash map frequency counting for array problems. Count occurrences, find duplicates, and solve majority element problems efficiently.
Work towards the solution in these steps:
- Track a value that could still be the majority while scanning the array.
- When the current value agrees with the candidate, strengthen its support; otherwise, weaken it.
- A value paired against a different value can cancel one occurrence of each without changing which value can have more than half of the total occurrences.
The reference solution runs in O(n) time and O(1) space.
The Majority Element solution and editorial walks through the full approach with reference code.
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
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
Majority Element FAQ
What is the LeetCode number of Majority Element?
Majority Element is LeetCode problem 169, rated Easy.
What pattern is used to solve Majority Element?
Majority Element is a Hashing Frequency Map and Counting problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.
What is the time complexity of Majority Element?
The reference solution runs in O(n) time and O(1) space.