Problem Statement: Given an array of N integers. Find the elements that appear more than N/3 times in the array. If no such element exists, return an empty vector.
Example 1:
Input: N = 5, array[] = {1,2,2,3,2}
Ouput: 2
Explanation: Here we can see that the Count(1) = 1, Count(2) = 3 and Count(3) = 1.Therefore, the count of 2 is greater than N/3 times. Hence, 2 is the answer.
Example 2:
Input: N = 6, array[] = {11,33,33,11,33,11}
Output: 11 33
Explanation: Here we can see that the Count(11) = 3 and Count(33) = 3. Therefore, the count of both 11 and 33 is greater than N/3 times. Hence, 11 and 33 is the answer.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute-Force
Approach: Simply count the no. of appearance for each element using nested loops and whenever you find the count of an element greater than N/3 times, that element will be your answer.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
vector < int > majorityElement(int arr[], int n) {
vector < int > ans;
for (int i = 0; i < n; i++) {
int cnt = 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] == arr[i])
cnt++;
}
if (cnt > (n / 3))
ans.push_back(arr[i]);
}
return ans;
}
int main() {
int arr[] = {1,2,2,3,2};
vector<int> majority;
majority = majorityElement(arr, 5);
cout << "The majority element is" << endl;
set < int > s(majority.begin(), majority.end());
for (auto it: s) {
cout << it << " ";
}
}
Output:
The majority element is 2
Time Complexity: O(n^2)
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main {
static ArrayList < Integer > majorityElement(int arr[], int n) {
ArrayList < Integer > ans = new ArrayList < > ();
for (int i = 0; i < n; i++) {
int cnt = 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] == arr[i])
cnt++;
}
if (cnt > (n / 3))
ans.add(arr[i]);
}
return ans;
}
public static void main(String args[]) {
int arr[] = {1, 2, 2, 3, 2};
ArrayList < Integer > majority = majorityElement(arr, 5);
System.out.print("The majority element is: ");
HashSet < Integer > s = new HashSet < > (majority);
for (int it: s) {
System.out.print(it + " ");
}
System.out.println();
}
}Output:
The majority element is: 2
Time Complexity: O(n^2)
Space Complexity: O(1)
Solution 2: Better Solution
Approach: Traverse the whole array and store the count of every element in a map. After that traverse through the map and whenever you find the count of an element greater than N/3 times, store that element in your answer.
Dry Run: Lets take the example of arr[] = {10,20,40,40,40}, n=5.
First, we create an unordered map to store the count of each element.
Now traverse through the array
- Found 10 at index 0, increase the value of key 10 in the map by 1.
- Found 20 at index 1, increase the value of key 20 in the map by 1.
- Found 40 at index 2, increase the value of key 40 in the map by 1.
- Found 40 at index 3, increase the value of key 40 in the map by 1.
- Found 40 at index 4, increase the value of key 40 in the map by 1.
Now, Our map will look like this:
10 -> 1
20 ->1
40 ->3
Now traverse through the map,
We found that the value of key 40 is greater than 2 (N/3). So, 40 is the answer.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
vector < int > majorityElement(int arr[], int n) {
unordered_map < int, int > mp;
vector < int > ans;
for (int i = 0; i < n; i++) {
mp[arr[i]]++;
}
for (auto x: mp) {
if (x.second > (n / 3))
ans.push_back(x.first);
}
return ans;
}
int main() {
int arr[] = {1,2,2,3,2};
vector < int > majority;
majority = majorityElement(arr, 5);
cout << "The majority element is " << ;
for (auto it: majority) {
cout << it << " ";
}
}Output: The majority element is: 2
Time Complexity: O(n)
Space Complexity: O(n)
Java Code
import java.util.*;
public class Main {
static ArrayList < Integer > majorityElement(int arr[], int n) {
HashMap < Integer, Integer > mp = new HashMap < > ();
ArrayList < Integer > ans = new ArrayList < > ();
for (int i = 0; i < n; i++) {
mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
}
for (int x: mp.keySet()) {
if (mp.get(x) > (n / 3))
ans.add(x);
}
return ans;
}
public static void main(String args[]) {
int arr[] = {1, 2, 2, 3, 2};
ArrayList < Integer > majority = majorityElement(arr, 5);
System.out.print("The majority element is: ");
HashSet < Integer > s = new HashSet < > (majority);
for (int it: s) {
System.out.print(it + " ");
}
System.out.println();
}
}Output:
The majority element is: 2
Time Complexity: O(n)
Space Complexity: O(n)
Solution 3: Optimal Solution (Extended Boyer Moore’s Voting Algorithm)
Approach + Intuition: In our code, we start with declaring a few variables:
- num1 and num2 will store our currently most frequent and second most frequent element.
- c1 and c2 will store their frequency relatively to other numbers.
- We are sure that there will be a max of 2 elements which occurs > N/3 times because there cannot be if you do a simple math addition.
Let, ele be the element present in the array at any index.
- if ele == num1, so we increment c1.
- if ele == num2, so we increment c2.
- if c1 is 0, so we assign num1 = ele.
- if c2 is 0, so we assign num2 = ele.
- In all the other cases we decrease both c1 and c2.
In the last step, we will run a loop to check if num1 or nums2 are the majority elements or not by running a for loop check.
Intuition: Since it’s guaranteed that a number can be a majority element, hence it will always be present at the last block, hence, in turn, will be on nums1 and nums2. For a more detailed explanation, please watch the video below.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
vector < int > majorityElement(int nums[], int n) {
int sz = n;
int num1 = -1, num2 = -1, count1 = 0, count2 = 0, i;
for (i = 0; i < sz; i++) {
if (nums[i] == num1)
count1++;
else if (nums[i] == num2)
count2++;
else if (count1 == 0) {
num1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
num2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
vector < int > ans;
count1 = count2 = 0;
for (i = 0; i < sz; i++) {
if (nums[i] == num1)
count1++;
else if (nums[i] == num2)
count2++;
}
if (count1 > sz / 3)
ans.push_back(num1);
if (count2 > sz / 3)
ans.push_back(num2);
return ans;
}
int main() {
int arr[] = {1,2,2,3,2};
vector < int > majority;
majority = majorityElement(arr, 5);
cout << "The majority element is ";
for (auto it: majority) {
cout << it << " ";
}
}
Output:
The majority element is 2
Time Complexity: O(n)
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main {
public static ArrayList < Integer > majorityElement(int[] nums) {
int number1 = -1, number2 = -1, count1 = 0, count2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
else if (count1 == 0) {
number1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
number2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
ArrayList < Integer > ans = new ArrayList < Integer > ();
count1 = 0;
count2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
}
if (count1 > len / 3)
ans.add(number1);
if (count2 > len / 3)
ans.add(number2);
return ans;
}
public static void main(String args[]) {
int arr[] = {1, 2, 2, 3, 2};
ArrayList < Integer > majority = majorityElement(arr);
System.out.print("The majority element is: ");
HashSet < Integer > s = new HashSet < > (majority);
for (int it: s) {
System.out.print(it + " ");
}
System.out.println();
}
}Output:
The majority element is: 2
Time Complexity: O(n)
Space Complexity: O(1)
Special thanks to Utkarsh Shrivastava for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article