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)
Python Code
from typing import List
def majorityElement(arr: List[int]) -> List[int]:
ans = []
for i in range(len(arr)):
cnt = 1
for j in range(i + 1, len(arr)):
if arr[j] == arr[i]:
cnt += 1
if cnt > (len(arr) / 3):
ans.append(arr[i])
return ans
if __name__ == "__main__":
arr = [1, 2, 2, 3, 2]
majority = majorityElement(arr)
print("The majority element is")
s = set(majority)
for it in s:
print(it, end=" ")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: Let’s 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)
Python Code
from typing import List
def majorityElement(arr: List[int]) -> List[int]:
mp = {}
ans = []
n = len(arr)
for i in range(n):
mp[arr[i]] = mp.get(arr[i], 0) + 1
for x in mp:
if mp[x] > n // 3:
ans.append(x)
return ans
if __name__ == "__main__":
arr = [1, 2, 2, 3, 2]
majority = majorityElement(arr)
print("The majority element is")
s = set(majority)
for it in s:
print(it, end=" ")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 by declaring a few variables:
- num1 and num2 will store our current most frequent and second most frequent elements.
- c1 and c2 will store their frequency relative to other numbers.
- We are sure that there will be a max of 2 elements that 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)
Python Code
from typing import List
def majorityElement(nums: List[int]) -> List[int]:
sz = len(nums)
num1 = -1
num2 = -1
count1 = 0
count2 = 0
for i in range(sz):
if nums[i] == num1:
count1 += 1
elif nums[i] == num2:
count2 += 1
elif count1 == 0:
num1 = nums[i]
count1 = 1
elif count2 == 0:
num2 = nums[i]
count2 = 1
else:
count1 -= 1
count2 -= 1
ans = []
count1 = count2 = 0
for i in range(sz):
if nums[i] == num1:
count1 += 1
elif nums[i] == num2:
count2 += 1
if count1 > sz // 3:
ans.append(num1)
if count2 > sz // 3:
ans.append(num2)
return ans
if __name__ == "__main__":
arr = [1, 2, 2, 3, 2]
majority = majorityElement(arr)
print("The majority element is")
s = set(majority)
for it in s:
print(it, end=" ")Output:
The majority element is: 2
Time Complexity: O(n)
Space Complexity: O(1)
Special thanks to Utkarsh Shrivastava and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article