Majority Element solution and explanation
Google
TCS
Infosys
IBM
9 more videos on this problem
Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimaltake U forward · 18:13 · 771K views
Majority Element - Leetcode 169 - PythonNeetCode · 14:39 · 181K views
Majority Element (LeetCode 169) | Full solution with 4 different methods | Interview EssentialNikhil Lohia · 15:15 · 58K views
Majority Element | Leetcode 169 |Moore's voting algorithm | Top 150 interview question seriesTechnosage · 12:22 · 46K views
Majority Element I | Majority Element II | Boyer-Moore | Made Simple | Leetcode 229 | Leetcode 169codestorywithMIK · 31:50 · 33K views
Majority Element - Leetcode 169 - Hashmaps & Sets (Python)Greg Hogg · 8:00 · 18K views
Leetcode | 169. Majority Element | Easy | Java SolutionDeveloper Docs · 4:34 · 7K views
The Genius Behind Boyer-Moore Voting | Majority Element Java Solution | LeetCode 169 | GeekificGeekific · 5:32 · 2K views
Majority Element - LeetCode 169 - Python #leetcode #majorityelement #votingalgorithmDeepti Talesra · 9:07 · 2K views
Can You Find Majority Element (LeetCode 169: Majority Element)Code With Zi · 6:48 · 2K views
The problem
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
O(1) space?Approach overview
Problem Overview: Given an integer array nums, return the element that appears more than ⌊n/2⌋ times. The problem guarantees that a majority element always exists, so at least one value occurs in more than half of the positions in the array.
Approach 1: HashMap Counting (O(n) time, O(n) space)
This approach uses a frequency map to count how many times each value appears. Iterate through the array and update counts in a hash table. As soon as a count exceeds n/2, return that number. Hash lookups and updates run in constant time on average, so the full scan remains linear. This approach is straightforward and easy to reason about, especially if you're already comfortable with hash tables and frequency counting patterns.
Approach 2: Sorting (O(n log n) time, O(1) space)
Sorting the array reveals a useful property of majority elements. If a number appears more than half the time, it must occupy the middle index after sorting. Sort the array and return the element at index n/2. This works because the majority element dominates the center of the sorted order. The tradeoff is the O(n log n) cost of sorting. This approach can still be practical when sorting utilities are readily available and memory use must remain minimal.
Approach 3: Boyer-Moore Voting Algorithm (O(n) time, O(1) space)
The Boyer-Moore Voting Algorithm is the optimal solution. It scans the array once while maintaining a candidate and a count. When the count drops to zero, the current element becomes the new candidate. Matching elements increase the count, while different elements decrease it. Because the majority element appears more than half the time, it cannot be fully canceled out by other values. After one pass, the candidate must be the majority element. This technique relies purely on counters and sequential iteration, making it extremely space efficient. It is a classic pattern when working with arrays and majority detection problems.
Recommended for interviews: The Boyer-Moore Voting Algorithm is what most interviewers expect. It demonstrates understanding of algorithmic optimization and achieves the best possible complexity: O(n) time and O(1) space. Starting with a HashMap explanation shows clear thinking about counting, but transitioning to Boyer-Moore shows stronger problem-solving ability. Some candidates also mention the divide and conquer perspective, but Boyer-Moore remains the most common optimal answer.
Approach 1: HashMap Counting Approach
This approach involves counting the frequency of each element using a HashMap (or a Dictionary). We store each element as a key and maintain its count as the value. Finally, we determine which key has a count greater than half the length of the array.
def majorityElement(nums):
counts = {}
for num in nums:
if num in counts:
counts[num] += 1
else:
counts[num] = 1
for num, count in counts.items():
if count > len(nums) // 2:
return num
print(majorityElement([2, 2, 1, 1, 1, 2, 2]))import java.util.HashMap;
import java.util.Map;
public class MajorityElement {
public static int majorityElement(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
int majorityCount = nums.length / 2;
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() > majorityCount) {
return entry.getKey();
}
}
return -1; // Unreachable code due to problem assumptions
}
public static void main(String[] args) {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
System.out.println(majorityElement(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int majorityElement(vector<int>& nums) {
unordered_map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
int majorityCount = nums.size() / 2;
for (auto& [num, count] : countMap) {
if (count > majorityCount) {
return num;
}
}
return -1; // never hit due to problem assumptions
}
int main() {
vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
cout << majorityElement(nums);
return 0;
}function majorityElement(nums) {
const counts = {};
for (const num of nums) {
counts[num] = counts[num] ? counts[num] + 1 : 1;
}
const majorityCount = Math.floor(nums.length / 2);
for (const num in counts) {
if (counts[num] > majorityCount) {
return parseInt(num);
}
}
return -1; // Unreachable in problem's context
}
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int majorityElement(int* nums, int numsSize) {
int *hashTable = (int*)calloc(2000000000, sizeof(int)); // Very large to accommodate range
int offset = 1000000000; // Offset for negative numbers
for (int i = 0; i < numsSize; i++) {
hashTable[nums[i] + offset]++;
}
for (int i = 0; i < numsSize; i++) {
if (hashTable[nums[i] + offset] > numsSize/2) {
free(hashTable);
return nums[i];
}
}
free(hashTable);
return -1;
}
int main() {
int nums[] = {2, 2, 1, 1, 1, 2, 2};
int size = sizeof(nums)/sizeof(nums[0]);
printf("%d", majorityElement(nums, size));
return 0;
}using System;
using System.Collections.Generic;
class MajorityElementSolver {
public static int MajorityElement(int[] nums) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
foreach (int num in nums) {
if (countMap.ContainsKey(num))
countMap[num]++;
else
countMap[num] = 1;
}
int majorityCount = nums.Length / 2;
foreach (var kvp in countMap) {
if (kvp.Value > majorityCount) {
return kvp.Key;
}
}
return -1; // Unreachable in problem's context
}
static void Main() {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
Console.WriteLine(MajorityElement(nums));
}
}Python utilizes a dictionary for counting, and then iterates through the dictionary to retrieve the majority element by scanning through its counts.
Time Complexity: O(n), Space Complexity: O(n) as dictionary storage grows linearly with input.
Approach 2: Boyer-Moore Voting Algorithm
The Boyer-Moore Voting Algorithm is an efficient solution that processes the array in a single pass. It maintains a count for the majority candidate. At the end of the loop, since the majority element exists, the candidate will be the majority element.
def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
print(majorityElement([2, 2, 1, 1, 1, 2, 2]))public class MajorityElement {
public static int majorityElement(int[] nums) {
int count = 0, candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
public static void main(String[] args) {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
System.out.println(majorityElement(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int majorityElement(vector<int>& nums) {
int count = 0, candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
int main() {
vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
cout << majorityElement(nums);
return 0;
}function majorityElement(nums) {
let count = 0, candidate = null;
for (const num of nums) {
if (count === 0) {
candidate = num;
}
count += (num === candidate) ? 1 : -1;
}
return candidate;
}
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));#include <stdio.h>
int majorityElement(int* nums, int numsSize) {
int count = 0, candidate = 0;
for (int i = 0; i < numsSize; i++) {
if (count == 0) {
candidate = nums[i];
}
count += (nums[i] == candidate) ? 1 : -1;
}
return candidate;
}
int main() {
int nums[] = {2, 2, 1, 1, 1, 2, 2};
int size = sizeof(nums)/sizeof(nums[0]);
printf("%d", majorityElement(nums, size));
return 0;
}using System;
class MajorityElementSolver {
public static int MajorityElement(int[] nums) {
int count = 0, candidate = 0;
foreach (int num in nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
static void Main() {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
Console.WriteLine(MajorityElement(nums));
}
}Python's implementation is concise, leveraging the same increment and decrement pattern that characterizes the Boyer-Moore algorithm.
Time Complexity: O(n), Space Complexity: O(1) because it operates directly on the input with minimal secondary storage.
Approach 3: Moore Voting Algorithm
The basic steps of the Moore voting algorithm are as follows:
Initialize the element m and initialize the counter cnt = 0. Then, for each element x in the input list:
- If
cnt = 0, thenm = xandcnt = 1; - Otherwise, if
m = x, thencnt = cnt + 1, otherwisecnt = cnt - 1.
In general, the Moore voting algorithm requires two passes over the input list. In the first pass, we generate the candidate value m, and if there is a majority, the candidate value is the majority value. In the second pass, we simply compute the frequency of the candidate value to confirm whether it is the majority value. Since this problem has clearly stated that there is a majority value, we can directly return m after the first pass, without the need for a second pass to confirm whether it is the majority value.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function majorityElement(nums: number[]): number {
let cnt: number = 0;
let m: number = 0;
for (const x of nums) {
if (cnt === 0) {
m = x;
cnt = 1;
} else {
cnt += m === x ? 1 : -1;
}
}
return m;
}func majorityElement(nums []int) int {
var cnt, m int
for _, x := range nums {
if cnt == 0 {
m, cnt = x, 1
} else {
if m == x {
cnt++
} else {
cnt--
}
}
}
return m
}impl Solution {
pub fn majority_element(nums: Vec<i32>) -> i32 {
let mut m = 0;
let mut cnt = 0;
for &x in nums.iter() {
if cnt == 0 {
m = x;
cnt = 1;
} else {
cnt += if m == x { 1 } else { -1 };
}
}
m
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function majorityElement($nums) {
$m = 0;
$cnt = 0;
foreach ($nums as $x) {
if ($cnt == 0) {
$m = $x;
}
if ($m == $x) {
$cnt++;
} else {
$cnt--;
}
}
return $m;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap Counting Approach | Time Complexity: O(n), Space Complexity: O(n) as dictionary storage grows linearly with input. |
| Boyer-Moore Voting Algorithm | Time Complexity: O(n), Space Complexity: O(1) because it operates directly on the input with minimal secondary storage. |
| Moore Voting Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n) | O(n) | General case when simplicity and clarity matter |
| Sorting | O(n log n) | O(1) or O(log n) | Useful when sorting is already required or memory must stay minimal |
| Boyer-Moore Voting Algorithm | O(n) | O(1) | Best interview solution with optimal time and constant space |
Frequently asked questions
Is Majority Element easy or hard?
Majority Element is classified as an Easy problem on LeetCode with an acceptance rate around 66%. The HashMap solution is straightforward, but recognizing and implementing the Boyer-Moore Voting Algorithm demonstrates deeper algorithm knowledge.
Majority Element Python/Java solution
Python and Java implementations commonly use either a HashMap for counting frequencies or the Boyer-Moore Voting Algorithm. The Boyer-Moore approach is preferred because it runs in O(n) time and O(1) space while requiring only two variables.
How to solve Majority Element in O(n)?
Use the Boyer-Moore Voting Algorithm. Iterate through the array while tracking a candidate and a count. Increase the count when the current element matches the candidate and decrease it otherwise; when the count reaches zero, select a new candidate.
What is the best approach for Majority Element?
The Boyer-Moore Voting Algorithm is the best approach. It finds the majority element in O(n) time using only O(1) extra space. The algorithm maintains a candidate and a counter that cancels out non-majority elements during a single pass through the array.
Is Majority Element asked at Google/Amazon/Meta?
Majority Element is a common interview question across companies like Amazon, Google, Meta, and Microsoft. It tests understanding of array traversal, frequency counting, and the Boyer-Moore Voting Algorithm optimization.
What data structure is used in Majority Element?
The problem can be solved using a hash table for frequency counting or by using constant variables in the Boyer-Moore Voting Algorithm. Both rely on scanning an array and tracking occurrences of elements.
What is the time complexity of Majority Element?
The optimal solution runs in O(n) time. Boyer-Moore Voting scans the array once while maintaining a running candidate. HashMap counting also runs in O(n) time but requires O(n) additional space for storing frequencies.