Majority Element II
Problem Description
Given an integer array of size n, find all elements that appear more than one-third of the time.
Example 1:
Input: nums = [3, 2, 3]
Output: [3]
Explanation:
- Total elements (n) = 3. We’re looking for numbers appearing more than 3/3 = 1 time.
- The number 3 appears twice, so the output is [3].
Example 2:
Input: nums = [1, 2]
Output: [1,2]
Explanation:
- Total elements (n) = 2. Any number appearing more than 2/3 (which is 0) counts.
- Both 1 and 2 appear once, so the output is [1, 2].
Constraints:
n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
Note: ⌊n/3⌋ means floor division or integer division, and we will be using integer division throughout this article.
Brute Force Approach:
The first idea that comes to mind is to check all the elements in the array. We can count how many times each element appears, and if an element appears more than one-third of the time (n/3), we’ll add it to the list and return it.
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 appears in the entire array.
If we find an element that appears more than one-third of the time, we’ll include it in our result as the majority element.
Easy right!!
But wait! Here’s something you need to observe.
At max, how many numbers can be present in an array of size n which have a frequency strictly more than n/3?
Okay! To satisfy the condition one element should appear at least (n/3+1) times.
So let’s check how many maximum elements we can get that satisfy the condition.
For one element:
If an element appears (n/3 + 1) times, it takes up a portion of the array, but still leaves enough room for other elements as,
(n/3+1) < n
So, it's possible for one element to satisfy this condition.
For two elements:
If two elements each appear (n/3 + 1) times, the total count would be:
(n/3 + 1)+(n/3 + 1) = 2*(n/3) + 2
Since 2n/3 + 2 is still less than or equals to n, for all n >= 4 , so, it’s possible for two elements to meet the condition.
For three elements:
If we try to have three elements each appear more than (n/3) times, the total would be:
(n/3 + 1)+(n/3 + 1)+(n/3 + 1) = n + 3
But this total exceeds the size of the array n, which is impossible.
Conclusion:
This proves that at most two elements can appear more than ⌊n/3⌋ times in any array since adding a third would exceed the total number of elements in the array.
Now, Let’s Walk Through This Example
Let’s have an array: [3, 4, 2, 2, 4, 3, 2, 4]
Our goal is to identify the elements that occur more than ⌊8/3⌋ times. Since there are 8 elements in total, we need to find numbers that appear at least 3 times in the array (because ⌊8/3⌋+1=3).
- Start with the first element: 3
3 appears at indices 0 and 5.
Total count = 2.
Check condition: Is 2≥3?
No. So, 3 is not a majority element. - Move to the next element: 4
4 appears at indices 1, 4, and 7.
Total count = 3.
Check condition: Is 3≥3?
Yes. So, 4 is a majority element. - Move to the next unique element: 2
2 appears at indices 2, 3, and 6.
Total count = 3.
Check condition: Is 3≥3?
Yes. So, 2 is also a majority element. - Next unique elements: 2 (already counted)
We don’t need to count 2 again since we already know its count. - Move to the next element: 3 (already counted)
We don’t need to count 3 again either. - Move to the next element: 2 (already counted)
No need to count 2 again. - Move to the last element: 4 (already counted)
No need to count 4 again.
After checking all elements:
- The numbers that occur more than three times in the array [3,4,2,2,4,3,2,4] are 4 and 2, as both appear 3 times.
Thus, the elements occurring more than ⌊8/3⌋= 2 times are 4 and 2.
Now, How to Code It Up?
Begin by initializing an empty list called results to store elements that meet the criteria.
Loop through each element in the array. For each element, check if it's already in the results list. If it is, skip to the next iteration.
If the element is unique, initialize a counter to count its occurrences. Loop through the array again to count how many times the current element appears. After counting, check if the occurrence count exceeds ⌊n/3⌋. If it does, add the element to the results list.
Repeat this process for all elements in the array. Finally, return the results list, which contains the elements that appear more than ⌊n/3⌋ times.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
// size of the nums
int size = nums.size();
// list of majority elements
vector<int> results;
// Loop through each element in the nums
for (int i = 0; i < size; i++) {
// Check if nums[i] is already in the results list
if (results.empty() || results[0] != nums[i]) {
// Counter for occurrences of nums[i]
int count = 0;
// Count the frequency of nums[i]
for (int j = 0; j < size; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
// Check if the frequency exceeds floor(n/3)
if (count > (size / 3)) {
// Add to results
results.push_back(nums[i]);
}
}
// Stop if we have found two majority elements
if (results.size() == 2)
break;
}
// Return the list of majority elements
return results;
}
};2. Java Try on Compiler
class Solution {
public List<Integer> majorityElement(int[] nums) {
// Size of the array
int size = nums.length;
// List of majority elements
List<Integer> results = new ArrayList<>();
// Loop through each element in the array
for (int i = 0; i < size; i++) {
// Check if nums[i] is already in the results list
if (results.isEmpty() || results.get(0) != nums[i]) {
// Counter for occurrences of nums[i]
int count = 0;
// Count the frequency of nums[i]
for (int j = 0; j < size; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
// Check if the frequency exceeds floor(n/3)
if (count > (size / 3)) {
// Add to results
results.add(nums[i]);
}
}
// Stop if we have found two majority elements
if (results.size() == 2)
break;
}
// Return the list of majority elements
return results;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
# Size of the array
size = len(nums)
# List of majority elements
results = []
# Loop through each element in the array
for i in range(size):
# Check if nums[i] is already in the results list
if not results or results[0] != nums[i]:
# Counter for occurrences of nums[i]
count = 0
# Count the frequency of nums[i]
for j in range(size):
if nums[j] == nums[i]:
count += 1
# Check if the frequency exceeds floor(n/3)
if count > (size // 3):
# Add to results
results.append(nums[i])
# Stop if we have found two majority elements
if len(results) == 2:
break
# Return the list of majority elements
return results4. Javascript Try on Compiler
var majorityElement = function (nums) {
// Size of the array
const size = nums.length;
// List of majority elements
const results = [];
// Loop through each element in the array
for (let i = 0; i < size; i++) {
// Check if nums[i] is already in the results list
if (results.length === 0 || results[0] !== nums[i]) {
// Counter for occurrences of nums[i]
let count = 0;
// Count the frequency of nums[i]
for (let j = 0; j < size; j++) {
if (nums[j] === nums[i]) {
count++;
}
}
// Check if the frequency exceeds Math.floor(n/3)
if (count > Math.floor(size / 3)) {
// Add to results
results.push(nums[i]);
}
}
// Stop if we have found two majority elements
if (results.length === 2) break;
}
// Return the list of majority elements
return results;
};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, output array of size 2, 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.
Can we optimize it?
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 hash table 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 stores 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 elements appears more than n/3 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?
We start by determining the size of the array, which helps us calculate the threshold for majority elements, defined as threshold = n/3 +1.
Next, we create a hash map to count the occurrences of each element in the array.
We loop through the array, updating the count of each element in the hash map. If an element's count reaches the threshold, we add it to our results list.
To ensure we only return at most two majority elements, we stop checking once we have found both.
Finally, we return the list of majority elements.
That’s the approach! Ready to see the code? Let’s go!
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
// Step 1: Determine the size of the array
int size = nums.size();
// Step 2: Initialize a hash map to count frequencies
unordered_map<int, int> frequencyMap;
// Calculate the threshold for majority elements
int threshold = (size / 3) + 1;
// Step 3: Count the occurrences of each element
vector<int> majorityElements; // List to store majority elements
for (int i = 0; i < size; i++) {
frequencyMap[nums[i]]++;
// Check if the current element has reached the threshold
if (frequencyMap[nums[i]] == threshold) {
majorityElements.push_back(nums[i]);
}
// Step 4: Limit the results to at most two majority elements
if (majorityElements.size() == 2)
break;
}
// Step 5: Return the list of majority elements
return majorityElements;
}
};2. Java Try on Compiler
class Solution {
public List<Integer> majorityElement(int[] nums) {
// Step 1: Determine the size of the array
int size = nums.length;
// Step 2: Initialize a hash map to count frequencies
Map<Integer, Integer> frequencyMap = new HashMap<>();
// Calculate the threshold for majority elements
int threshold = (size / 3) + 1;
// Step 3: Count the occurrences of each element
List<Integer> majorityElements = new ArrayList<>();
// List to store majority elements
for (int i = 0; i < size; i++) {
frequencyMap.put(nums[i], frequencyMap.getOrDefault(nums[i], 0) + 1);
// Check if the current element has reached the threshold
if (frequencyMap.get(nums[i]) == threshold) {
majorityElements.add(nums[i]);
}
// Step 4: Limit the results to at most two majority elements
if (majorityElements.size() == 2) break;
}
// Step 5: Return the list of majority elements
return majorityElements;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
# Step 1: Determine the size of the array
size = len(nums)
# Step 2: Initialize a dictionary to count frequencies
frequency_map = {}
# Calculate the threshold for majority elements
threshold = (size // 3) + 1
# Step 3: Count the occurrences of each element
majority_elements = [] # List to store majority elements
for element in nums:
frequency_map[element] = frequency_map.get(element, 0) + 1
# Check if the current element has reached the threshold
if frequency_map[element] == threshold:
majority_elements.append(element)
# Step 4: Limit the results to at most two majority elements
if len(majority_elements) == 2:
break
# Step 5: Return the list of majority elements
return majority_elements
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function (nums) {
// Step 1: Determine the size of the array
const size = nums.length;
// Step 2: Initialize a map to count frequencies
const frequencyMap = new Map();
// Calculate the threshold for majority elements
const threshold = Math.floor(size / 3) + 1;
// Step 3: Count the occurrences of each element
const majorityElements = []; // List to store majority elements
for (const element of nums) {
frequencyMap.set(element, (frequencyMap.get(element) || 0) + 1);
// Check if the current element has reached the threshold
if (frequencyMap.get(element) === threshold) {
majorityElements.push(element);
}
// Step 4: Limit the results to at most two majority elements
if (majorityElements.length === 2) break;
}
// Step 5: Return the list of majority elements
return majorityElements;
};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?
In the problem of finding elements that appear more than one-third of the time in an array, we can use a game analogy similar to what we did for the Majority Element problem.
This time, we need to keep in mind that there can be at most two teams, or elements, that are dominant.
Imagine we're back in the arena where teams are battling it out, and we need to keep track of two teams that could potentially have more than one-third of the total players.
In this scenario, we won’t allow the two teams we’re tracking to collide with each other because if both teams were to face off against each other, one would inevitably be eliminated, which could lead to losing track of a potential majority candidate.
Instead, each of them will face off against other teams independently.
Let’s say we’re tracking two teams: Team A and Team B (let’s call them candidates). We believe they might meet the criteria of having a strong presence in the arena.
As the game unfolds, let us have four teams
Team A(45 players)
Team B(41 players)
Team C(34 players)
Team D(25 players)
Let’s say,
Team A collides with Team C. In this encounter, Team C loses the battle, and Team A remains strong, still holding its ground.
Later, Team B faces off against Team D. Team B wins this clash, maintaining its position in the arena.
Here the teams that we were tracking (Team A and Team B) successfully emerged as winners.
If at any point, one of the teams we’re tracking faces another team and loses, we don’t simply abandon our search. Instead, we start tracking the team that just defeated our candidate.
For instance, if Team A collides with Team E, which has 40 players, and loses, we recognize Team E as a strong contender. In this case, we shift our focus to Team E instead of continuing to track Team A. Similarly, if Team B encounters Team F, which has 50 players, and loses, we switch our attention to Team F.
We continue this process, keeping an eye on the two strongest teams and switching our focus to any new team that emerges victorious over our candidates.
This strategy allows us to stay aware of the strongest contenders in the game while ensuring that our candidates do not face off against each other.
Let’s consider this example:
Now, let’s consider a scenario with a total of 120 players in the arena. For a team to be considered dominant, it must have more than one-third of the players.
Since 120/3=40, a team needs at least 41 players to truly dominate.
Initially, we have Team A with 45 players and Team B with 41 players, while Team C has 34 players.
As the game progresses, we track the two dominant teams, Team A and Team B, since they each have more than one-third of the players.
In the first collision, Team A, with its 45 players, collides with Team C, which has 34 players. Given Team A's strength, it is likely that Team C will be eliminated or lose significant numbers, allowing Team A to maintain its strong position in the game.
In the next round, Team B, with 41 players, faces Team C again. Since Team C is already weakened from its previous encounter, it is probable that Team B will win this battle as well, enabling both Team A and Team B to remain strong contenders in the arena.
This entire setup helps us efficiently identify the teams that are likely to dominate, ensuring we’re always on the lookout for teams with a strong presence, and ultimately allows us to find the elements in the array that appear more than one-third of the time.
We learned about Moore’s Voting Algorithm in the Majority Element problem, where we figured out that a majority element will always dominate others.
The algorithm allows us to track a candidate, increase the count when we see the same element, and decrease it when we see a different one. In the end, the count stays positive for the majority element.
But in this problem, we need to find at most two majority elements. So, instead of one candidate and one count, we’ll track two candidates and two counts (as we tracked two teams).
How does it work?
Firstly, we’ll take two variables count1 and count2 for tracking the count of two majority elements.
Simple! If count1 is 0, we assign the current element as candidate1. If count2 is 0, we assign it as candidate2. For each element, if it matches candidate1, we increase count1; if it matches candidate2, we increase count2. Otherwise, if the element matches neither, we decrease both counts.
But wait—what if we already included an element in candidate1 and count2 is 0? It can repeat in candidate2 as well as count2 is 0. To prevent duplicates, we add a simple check: make sure candidate1 and candidate2 are different before assigning them (like we didn’t make two tracking teams fight with each other).
With this, the approach handles up to two potential majority elements, and once we've gone through the array, we can confirm their counts.
Let’s understand it with an example
Let’s have an array [3, 4, 2, 2, 4, 3, 2, 4]
Initialization:
- candidate1 = null, count1 = 0
- candidate2 = null, count2 = 0
Iterating over the array:
- Element: 3
count1 == 0:
Set candidate1 = 3, count1 = 1
Current state:
candidate1 = 3, count1 = 1
candidate2 = null, count2 = 0 - Element: 4
count2 = 0:
Set candidate2 = 4, count2 = 1
Current state:
candidate1 = 3, count1 = 1
candidate2 = 4, count2 = 1 - Element: 2
2 is neither candidate1 nor candidate2:
Decrement both count1 and count2
Current state: candidate1 = 3, count1 = 0
candidate2 = 4, count2 = 0 - Element: 2
count1 == 0:
Set candidate1 = 2, count1 = 1
Current state:
candidate1 = 2, count1 = 1
candidate2 = 4, count2 = 0 - Element: 4
Candidate2 == 4: Increment count2
Current state:
candidate1 = 2, count1 = 1
candidate2 = 4, count2 = 1 - Element: 3
3 is neither candidate1 nor candidate2:
Decrement both count1 and count2
Current state:
candidate1 = 2, count1 = 0
candidate2 = 4, count2 = 0 - Element: 2
count1 = 0:
Set candidate1 = 2, count1 = 1
Current state:
candidate1 = 2, count1 = 1
candidate2 = 4, count2 = 0 - Element: 4
candidate == 4: Increment count2
Final state after iteration:
candidate1 = 2, count1 = 1
candidate2 = 4, count2 = 1
Post-processing:
- Count occurrences of candidate1 (2) and candidate2 (4) in the array:
- 2 appears 3 times
- 4 appears 3 times
- Since both counts are greater than or equal to n/3 + 1 (which is 3), both 2 and 4 are majority elements.
Output:
- Majority elements are [2, 4].
How to Convert It into Code?
We start by initializing four variables:
- count1 and count2 to track the counts of two potential majority elements.
- candidate1 and candidate2 to store the two possible majority elements.
Next, we traverse through the array:
If count1 is 0 and the current element is not candidate2, we assign the current element as candidate1 and increase count1 by 1.
Else If count2 is 0 and the current element is not candidate1, we assign the current element as candidate2 and increase count2 by 1.
Else If the current element matches candidate1, we increment count1.
Else If the current element matches candidate2, we increment count2.
Else the current element matches neither candidate1 nor candidate2, we decrease both count1 and count2 by 1.
After traversing the array, candidate1 and candidate2 are the two potential majority elements. We then check their counts in another loop to confirm if they appear more than floor(N/3) times, and those that do are returned as the final majority elements.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
// size of the array
int n = nums.size();
// counts for two potential majority elements
int count1 = 0, count2 = 0;
// first candidate for majority
int candidate1 = INT_MIN;
// second candidate for majority
int candidate2 = INT_MIN;
// Extended Boyer-Moore's Voting Algorithm to find potential majority elements
for (int i = 0; i < n; i++) {
if (count1 == 0 && candidate2 != nums[i]) {
// Assign new candidate1 if count1 is zero and nums[i] is not candidate2
count1 = 1;
candidate1 = nums[i];
}
else if (count2 == 0 && candidate1 != nums[i]) {
// Assign new candidate2 if count2 is zero and nums[i] is not candidate1
count2 = 1;
candidate2 = nums[i];
} else if (nums[i] == candidate1) {
// If nums[i] matches candidate1, increment count1
count1++;
} else if (nums[i] == candidate2) {
// If nums[i] matches candidate2, increment count2
count2++;
} else {
// If nums[i] doesn't match either candidate, decrement both counts
count1--, count2--;
}
}
// list to store final majority elements
vector<int> result;
// Verify if the stored candidates are actually majority elements
count1 = 0, count2 = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == candidate1)
count1++;
if (nums[i] == candidate2)
count2++;
}
// threshold for majority elements (more than n/3)
int threshold = n / 3 + 1;
if (count1 >= threshold)
result.push_back(candidate1);
if (count2 >= threshold)
result.push_back(candidate2);
return result;
}
};2. Java Try on Compiler
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
int count1 = 0, count2 = 0;
int candidate1 = Integer.MIN_VALUE;
int candidate2 = Integer.MIN_VALUE;
// Extended Boyer-Moore Voting Algorithm to find potential majority elements
for (int num : nums) {
if (count1 == 0 && candidate2 != num) {
count1 = 1;
candidate1 = num;
} else if (count2 == 0 && candidate1 != num) {
count2 = 1;
candidate2 = num;
} else if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else {
count1--;
count2--;
}
}
// Verify if candidates are majority elements
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
if (num == candidate2) count2++;
}
List < Integer > result = new ArrayList <> ();
int threshold = n / 3 + 1;
if (count1 >= threshold) result.add(candidate1);
if (count2 >= threshold) result.add(candidate2);
return result;
}
}3. Python Try on Compiler
class Solution(object):
def majorityElement(self, nums):
n = len(nums)
count1, count2 = 0, 0
candidate1, candidate2 = float('-inf'), float('-inf')
# Extended Boyer-Moore Voting Algorithm to find potential majority elements
for num in nums:
if count1 == 0 and candidate2 != num:
count1 = 1
candidate1 = num
elif count2 == 0 and candidate1 != num:
count2 = 1
candidate2 = num
elif num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
else:
count1 -= 1
count2 -= 1
# Verify if candidates are majority elements
count1, count2 = 0, 0
for num in nums:
if num == candidate1:
count1 += 1
if num == candidate2:
count2 += 1
result = []
threshold = n // 3 + 1
if count1 >= threshold:
result.append(candidate1)
if count2 >= threshold:
result.append(candidate2)
return result4. Javascript Try on Compiler
var majorityElement = function (nums) {
const n = nums.length;
let count1 = 0, count2 = 0;
let candidate1 = Number.MIN_SAFE_INTEGER;
let candidate2 = Number.MIN_SAFE_INTEGER;
// Extended Boyer-Moore Voting Algorithm to find potential majority elements
for (let num of nums) {
if (count1 === 0 && candidate2 !== num) {
count1 = 1;
candidate1 = num;
} else if (count2 === 0 && candidate1 !== num) {
count2 = 1;
candidate2 = num;
} else if (num === candidate1) {
count1++;
} else if (num === candidate2) {
count2++;
} else {
count1--;
count2--;
}
}
// Verify if candidates are majority elements
count1 = 0;
count2 = 0;
for (let num of nums) {
if (num === candidate1) count1++;
if (num === candidate2) count2++;
}
const result = [];
const threshold = Math.floor(n / 3) + 1;
if (count1 >= threshold) result.push(candidate1);
if (count2 >= threshold) result.push(candidate2);
return result;
};Time Complexity: O(n)
The time complexity of our algorithm is O(n). This is because we iterate over the array from index i=0 to i=n.
Space Complexity: O(n)
Auxiliary Space: O(1)
Explanation: The auxiliary space is O(1) since the algorithm requires only four variables (candidate1, candidate2, and count1, count2) and an array of size 2, and does not use any additional data structures.
Total Space Complexity: O(n)
Explanation: We are using an input array of size 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.
You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:
- answer1 : the number of indices i such that nums1[i] exists in nums2.
- answer2 : the number of indices i such that nums2[i] exists in nums1.
Return [answer1,answer2].
Given an integer array nums, return the most frequent even element.
If there is a tie, return the smallest one. If there is no such element, return -1.