Majority Element
Problem Description
You are given an array of numbers, and your job is to find a number that shows up more than half the time in the array.
Examples of Majority Element
Example 1:
Input: nums = [3, 2, 3]
Output: 3
Explanation:
In this array, the number 3 appears twice, and the number 2 appears once. Since 3 appears more than half the time (which is 2 out of 3 elements), it is the desired element.
Example 2:
Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation:
In this array, 2 appears four times, and 1 appears three times. Since 2 appears more than half the time (which is 4 out of 7 elements), it is the desired element.
Constraints:
n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
Brute Force Approach:
Now, the first thing that comes to mind is to check all the elements in the array. We can count how many times each element appears.
How do we do this?
- We’ll go through the array one element at a time.
- For each element, we’ll count how often it shows up in the entire array.
- If we find an element that appears more than half the time, we return that as the majority element.
Let’s Walk Through This Example
Let’s have an array: [2, 3, 4, 4, 4]
Our goal is to find the majority element, which is the number that appears more than half the time. Since there are 5 elements in total, we’re looking for the number that appears more than 2 times (because 5 // 2 = 2 (integer division)).
Now let’s go through the array:
- Start with the first element, 2.
Now, we count how many times 2 appears: 2 appears only 1 time ([2]).
Is 1 more than 2?
No, so 2 can’t be the majority element. - Check the next element, 3.
Now, we count how many times 3 appears: 3 appears 1 time ([3]).
Is 1 more than 2?
No, so 3 isn’t the majority either. - Next, check 4.
We count how many times 4 appears in the array: 4 appears 3 times ([4, 4, 4]).
Is 3 more than 2?
Yes! So 4 is the majority element, so return 4.
After checking all the elements, the number 4 appears 3 times, which is more than half of the array size (5). So, the majority element in this array is 4.
Now, How to Code It Up?
To write the solution in code, we would start by creating a variable to keep track of how many times each number appears in the array.
Then, we would loop through each element, one by one. For every element we check, we count how many times it shows up in the entire array by again looping through the entire array.
Once we have that count, we look to see if it’s greater than half the size of the array.
If we have five elements, we’re looking for a count greater than two. If we find a number that meets that condition, we will return it as the majority element.
After checking each element, if we find one that appears more than half the time, we’re done! and since the problem states that there will always be a majority element, we can be confident that we’ll find it during our checks.
This way, we can write the code to find the majority element!
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// Initialize count for the current element
int count = 0;
// Count occurrences of the current element
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
// Check if the count is greater than n/2
if (count > n / 2) {
// Return the majority element
return nums[i];
}
}
// This line is not needed as the majority element is guaranteed to
// exist
return -1;
}
};2. Java Try on Compiler
class Solution {
public static int majorityElement(int[] nums) {
int n = nums.length;
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// Initialize count for the current element
int count = 0;
// Count occurrences of the current element
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
// Check if the count is greater than n/2
if (count > n / 2) {
// Return the majority element
return nums[i];
}
}
// This line is not needed as the majority element is guaranteed to exist
return -1;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
n = len(nums)
# Iterate through each element in the array
for i in range(n):
# Initialize count for the current element
count = 0
# Count occurrences of the current element
for j in range(n):
if nums[j] == nums[i]:
count += 1
# Check if the count is greater than n/2
if count > n // 2:
# Return the majority element
return nums[i]
# This line is not needed as the majority element is guaranteed to exist
return -1 4. Javascript Try on Compiler
var majorityElement = function(nums) {
const n = nums.length;
// Iterate through each element in the array
for (let i = 0; i < n; i++) {
// Initialize count for the current element
let count = 0;
// Count occurrences of the current element
for (let j = 0; j < n; j++) {
if (nums[j] === nums[i]) {
count++;
}
}
// Check if the count is greater than n/2
if (count > Math.floor(n / 2)) {
// Return the majority element
return nums[i];
}
}
// This line is not needed as the majority element is guaranteed to exist
return -1;
};Time Complexity: O(n²)
For each element in the array, we traverse the entire array to count its occurrences. In the first loop, we go from index 0 to n, and for each iteration of this loop, we again traverse from index 0 to n in the second loop. This can be expressed as n + n + n + n…, repeated n times. Thus, the time complexity can be expressed as O(n) * O(n), resulting in a total time complexity of O(n²).
Space Complexity: O(n)
Auxiliary Space: O(1)
Explanation: The auxiliary space used by the algorithm is O(1) since we're only using a fixed number of variables, regardless of the input size.
Total Space Complexity: O(n)
Explanation: While the algorithm itself uses only a few variables (like count and other constants), we still need to store the input array of size n. This means the total space complexity is at least O(n) due to the input.
So, the overall space complexity is dominated by the input array, making it O(n).
Will Brute Force Work Against the Given Constraints?
Let’s consider if the brute force method will work with the constraints we’re given. The problem mentions that the array size, n, can go up to 50,000.
With a brute force approach, we would use a nested loop to count how many times each element appears. This means that for each element, we would have to go through the entire array again, resulting in n * n comparisons.
Now, if n is 50,000, then n * n equals 2.5 billion (i.e 2.5*10⁹) operations. That’s way too many because most competitive programming environments can handle around 10⁷ to 10⁸ operations within the given time limits.
This approach would have worked if n were smaller—say, up to 1,000. In that case, the total number of operations would be around 10⁶ (1 million), which is manageable within typical time constraints for most competitive programming problems.
However, with larger values of n, the brute force method becomes impractical.
So, while the brute force approach will technically work and give the right answer, it’s far from efficient when dealing with larger input sizes and can’t handle the upper limits of the constraints.
Optimization of Majority Element Problem
In the brute force approach, we're calculating the frequency of each element multiple times, which makes it slower. Instead, how about we calculate the frequency of each element just once?
What if we could count the occurrences of all the elements, indicating how many times they are present? This would eliminate the need for the second loop to traverse the array entirely.
We need a data structure that allows us to know the frequency of elements in constant time, so we can instantly determine how many times an element is present without having to go through the entire list. This significantly improves the efficiency of the process.
Which data structure can be found useful here?
Yes, you’re right! We could use something like a hashtable to store the count of each element as we go through the array.
What is a hash table?
A hash table can be thought of as an auxiliary array where each index stores data linked to a specific key. The hash function computes the index in this auxiliary array for a given key, allowing direct access to the stored value. This structure ensures fast operations since accessing an index in an array is an O(1) operation.
But wait—our elements range from -10⁹ to 10⁹, meaning the numbers can be both negative and spread across a huge range. Building a hash table with such a large range would lead to inefficient memory usage, as we'd need an enormous table to account for all possible values.
So, how do we tackle this?
The answer is hash maps. Unlike arrays or hash tables with fixed sizes, a hash map dynamically stores only the elements we encounter, along with their counts. This way, we avoid wasting memory on values that don't exist in the array, making the solution both space-efficient and faster.
What are hash maps?
Hash maps are a powerful data structure that store key-value pairs, allowing for fast access to values using their keys. They are used to determine where to store each pair, enabling average-case time complexities of O(1) for insertion, search, and deletion.
Once we've built this frequency map, we can simply check which element appears more than n/2 times and return that as the majority element.
This way, we're reducing the extra work and bringing the time complexity down to O(n), which is much faster and will work more efficiently with larger inputs.
Doesn’t that sound like a great step forward? Let’s go for it!
Let's Walk Through This Example
Now, How to Code It Up?
Let’s jump into coding our optimized solution!
First, we’ll need to set up our hash map to count the frequencies of each number in the array.
We’ll create an empty object for our hash map. Then, we'll loop through the array to populate this map with counts.
Once we have the counts, we’ll loop through the hash map to find the element that appears more than n/2 times. Finally, we’ll return that element.
It’s pretty straightforward! The key steps are counting the frequencies and then checking for the majority.
Are you ready to see the code? Let’s do this!
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Create a hash map to store counts
unordered_map<int, int> countMap;
for (int num : nums) {
// Increment the count for the current number
countMap[num]++;
}
// Find the majority element
for (auto& entry : countMap) {
if (entry.second > nums.size() / 2) {
// Return the element if its count is greater than n/2
return entry.first;
}
}
// This line won't be reached as per the problem's guarantee
return -1;
}
};2. Java Try on Compiler
class Solution {
public int majorityElement(int[] nums) {
// Create a hash map to store counts
HashMap<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
// Increment the count for the current number
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
// Find the majority element
for (int key : countMap.keySet()) {
if (countMap.get(key) > nums.length / 2) {
// Return the element if its count is greater than n/2
return key;
}
}
// This line won't be reached as per the problem's guarantee
return -1;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
# Create a hash map to store counts
countMap = {}
for num in nums:
# Increment the count for the current number
countMap[num] = countMap.get(num, 0) + 1
# Find the majority element
for key, count in countMap.items():
if count > len(nums) // 2:
# Return the element if its count is greater than n/2
return key
# This line won't be reached as per the problem's guarantee
return -1
4. Javascript Try on Compiler
var majorityElement = function(nums) {
// Create a hash map to store counts
const countMap = {};
for (const num of nums) {
// Increment the count for the current number
countMap[num] = (countMap[num] || 0) + 1;
}
// Find the majority element
for (const key in countMap) {
if (countMap[key] > nums.length / 2) {
// Return the element if its count is greater than n/2
return parseInt(key);
}
}
// This line won't be reached as per the problem's guarantee
return -1;
};Time Complexity: O(n)
As we iterate through the array from index 0 to n, the time complexity for this step is O(n). After that, we also iterate through the hash map, which, in the worst case (when all elements are different), can have a size of n, resulting in another O(n) operation. Since both loops are independent of each other, we can combine the time complexities:
O(n) + O(n) = O(n). Therefore, the overall time complexity remains O(n).
Space Complexity: O(n)
We use a hash map to store the count of each number in the array. In the worst case, if all elements are unique, the hash map will contain n entries, where n is the size of the array. Therefore, the space required to hold these counts leads to a space complexity of O(n).
Consequently, the overall space complexity of our solution is O(n).
Can there be a better approach?
Yes, there’s definitely a smarter way to solve this problem—one that works in linear time and uses constant space.
Want to know how?
Imagine a big multiplayer game where several teams are playing together. Each team has a bunch of players, and the goal is to eliminate the players from other teams.
Here’s the twist: when two players from different teams collide or fight, both of them get eliminated. So, every time players from two teams meet, they both lose one player. Now, let's say one team has more than half the total players—that team is the majority.
Here’s how it plays out:
When a player from the majority team faces off with a player from a smaller team, both are eliminated, but the majority team will still have more players left.
The majority team keeps losing players in these fights, but it can always afford to because it started with more players than anyone else.
Even if the majority team goes through multiple battles, it will always have some players left because no other team can match its numbers. At the end of the game, all the smaller teams will be eliminated, and only the majority team will survive.
For example, let’s say there are 100 players in total, and the majority team has 51 players (since 51 is more than half of 100). All the other teams together have 49 players. Let’s walk through this step by step:
The first time a player from the majority team (51 players) collides with a player from the smaller teams (49 players), both are eliminated. Now, the majority team has 50 players, and the smaller teams combined have 48 players.
This process keeps repeating—each time a player from the majority team collides with a player from the other team, both are eliminated. After several battles, the numbers continue to decrease:
Majority team: 50 → 49 → 48 → 47…Other teams: 48 → 47 → 46 → 45...
After 49 collisions, all players from the smaller teams are eliminated. The majority team still has 2 players left, while the smaller teams have none.
Even after all these collisions, the majority of the team survives with 2 players.
Now suppose we have three teams, Team A with 51 players, Team B with 25 players, and Team C with 25 players.players. for Team A, as it secures victory while preserving the maximum number of its players.
No matter how many fights they go through, the majority team will always have players left because they started with more than half the total number of players.
In the same way, think about an array of numbers. If there's an element that appears more than half the time, it acts just like the majority team in the game. As we go through the array:
Whenever we encounter the majority element, it "survives" and stays in the lead.
If we encounter a different element, it's like a battle where one player from the majority element "fights" with the new element, and they both get eliminated, reducing the count of the majority element.
But since the majority element appears more than half the time, it will always stay ahead in the game of eliminations, just like the team with the most players.
In the end, even after all the encounters with other elements, the majority element will be the one left standing—just like the majority team wins in the game!
So, just like the strongest team with more than half the players wins in the game, the majority element in an array is the one that will always "survive" and be left at the end of our process.
Using this idea, we can efficiently find the majority element in an array. Simple and effective!
Video Explanation - Majority Element in an array
The main idea is simple: if there's a majority element in an array, it will always "win" over the other elements, even if we encounter different ones.
Here’s how it works:
Imagine we have an array where most of the elements are 1, and the rest are -1. If we sum this array, the result will always be positive, right? That's because each 1 cancels out a -1, and since 1 is the majority, it remains in the end.
Similarly, when we compare the majority element with other elements, the majority will always "survive" because it's more frequent.
Now, let’s break it down:
- Let’s say we have a majority element in the array, which we'll call the candidate.
- As we move through the array, we increase the count if we see the same the and decrease it if we encounter a different element.
The count for the candidate will always stay positive because it appears more than any other element (since it's the majority).
But wait, how do we know what the majority element is in the first place?
Here’s the clever part: we start with no candidate and a count of zero. As we go through the array, we can take the first element as our candidate and start by increasing the count. Then, as we continue:
- If an element matches the current candidate, we increase the count.
- If it doesn’t match, we decrease the count.
- When the count drops to zero, we pick the current element as the new candidate and reset the count.
By the time we finish going through the array, the candidate we’re left with will be the majority element because the count will always stay positive for the majority element.
Simple, right?
Now, Let's see this in action with an example!
Imagine we have the array: [3, 3, 4, 2, 4, 4, 2, 4, 4].
- Step 1: We start by picking the first number, which is 3, and set it as our candidate. We also initialize a count for it, starting at 1.
candidate: 3
count: 1
- Step 2: As we move to the next number, which is also 3, we increase the count because it's the same as our candidate. Now, the count is 2.
candidate: 3
count: 2
- Step 3: Next, we see a 4. This isn’t the same as our current candidate (3), so we decrease the count. Now, the count is 1.
candidate: 3
count: 1
- Step 4: We move to 2. Since it's not equal to 3, we decrease the count again. Now, the count is 0.
candidate: 3
count: 0
- Step 5: Since the count has dropped to 0, we reset our candidate. The next number is 4, so we make 4 our new candidate and reset the count to 1.
candidate: 4
count: 1
- Step 6: Moving on, we see another 4. This matches our candidate, so we increase the count to 2.
candidate: 4
count: 2
- Step 7: We see a 2. It doesn’t match our candidate (4), so we decrease the count to 1.
candidate: 4
count: 1
- Step 8: The next two numbers are both 4, and since they match our candidate, we increase the count to 3.
candidate: 4
count: 3
By the end of this process, our candidate is 4 and the count is positive, meaning that 4 is the majority element.
This approach is also called Moore’s Voting algorithm.
How to Convert It into Code?
Turning this idea into code is actually quite simple! We just need two variables: one for the candidate and another for the count.
First, we initialize the candidate to null and the count to 0. Then, we go through each element in the array:
If the count is 0, we set the current element as the new candidate.
If the current element matches the candidate, we increase the count.
If it doesn’t match, we decrease the count.
By the end of the array, the candidate will hold the majority element.
This approach gives us a very efficient solution that works in just one pass through the array, making it O(n) in time and using constant space.
Ready to see it in code? Let’s dive into the implementation!
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Initialize count to 0
int count = 0;
// Initialize candidate to 0
int candidate = 0;
// Iterate through each number in the array
for (int num : nums) {
if (count == 0) {
// When count is 0, set current number as the new candidate
candidate = num;
}
// Increase count if current number matches candidate
if (num == candidate) {
count++;
} else {
// Otherwise, decrease the count
count--;
}
}
// Return the candidate which is the majority element
return candidate;
}
};2. Java Try on Compiler
class Solution {
public int majorityElement(int[] nums) {
// Initialize count to 0
int count = 0;
// Initialize candidate to 0
int candidate = 0;
// Iterate through each number in the array
for (int num : nums) {
if (count == 0) {
// When count is 0, set the current number as the new candidate
candidate = num;
}
// Increase count if current number matches candidate
if (num == candidate) {
count++;
} else {
// Otherwise, decrease the count
count--;
}
}
// Return the candidate which is the majority element
return candidate;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
# Initialize count to 0
count = 0
# Initialize candidate to 0
candidate = 0
# Iterate through each number in the array
for num in nums:
if count == 0:
# When count is 0, set the current number as the new candidate
candidate = num
# Increase count if the current number matches the candidate
if num == candidate:
count += 1
else:
# Otherwise, decrease the count
count -= 1
# Return the candidate which is the majority element
return candidate
4. Javascript Try on Compiler
var majorityElement = function (nums) {
// Initialize count to 0
let count = 0;
// Initialize candidate to 0
let candidate = 0;
// Iterate through each number in the array
for (let num of nums) {
if (count === 0) {
// When count is 0, set the current number as the new candidate
candidate = num;
}
// Increase count if the current number matches the candidate
if (num === candidate) {
count++;
} else {
// Otherwise, decrease the count
count--;
}
}
// Return the candidate which is the majority element
return candidate;
};Time Complexity: O(n)
The time complexity of our algorithm is O(n). This is because we iterate over the array exactly once, from index i=0 to i=n.
Space Complexity: O(n)
We are using an input array of size n. However, aside from the input, we only use two variables, candidate and count, which means the extra space we use is constant.
Auxiliary Space: O(1)
Explanation: The auxiliary space is O(1) since the algorithm requires only two variables (candidate and count) and does not use any additional data structures.
Total Space Complexity: O(n)
Thus, the total space complexity is dominated by the input array, making it O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
You are given two lists of numbers. The first list is called nums1 and the second list is called nums2. Your task is to find