You are given an array 'a' of 'n' integers.
A majority element in the array ‘a’ is an element that appears more than 'n' / 2 times.
Find the majority element of the array.
It is guaranteed that the array 'a' always has a majority element.
Input: ‘n’ = 9, ‘a’ = [2, 2, 1, 3, 1, 1, 3, 1, 1]
Output: 1
Explanation: The frequency of ‘1’ is 5, which is greater than 9 / 2.
Hence ‘1’ is the majority element.
The first line contains one integer ‘n’, denoting the number of elements in the array ‘a’.
The second line contains ‘n’ integers denoting the elements of the array ‘a’.
Return the majority element.
You do not need to print anything; it has already been taken care of. Just implement the given function.
9
2 2 1 3 1 1 3 1 1
1
Input: ‘n’ = 9, ‘a’ = [2, 2, 1, 3, 1, 1, 3, 1, 1]
Output: 1
Explanation: The frequency of ‘1’ is 5, which is greater than 9 / 2.
Hence ‘1’ is the majority element.
1
4
4
5
-53 75 56 56 56
56
The expected time complexity is O(n).
1 <= 'n' <= 10000
0 <= 'arr[i]' <= 10^9
Time limit: 1 second
Use a nested loop to count frequency.
The naive approach to solving the problem is to use two nested loops. The first loop will iterate over all the elements of the array ‘a’ one by one. In each iteration, the second loop will calculate the frequency of this element in the whole array by again iterating over the whole array. If the frequency of this element > floor(n / 2), then we can stop the program and return this element as we have found the majority element.
The steps are as follows:-
// Function to find the majority element
function majorityElement(int a[], int n):
O(n ^ 2), where ‘n’ is the number of elements.
We are using two nested loops.
Hence the time complexity is O(n ^ 2).
O(1).
We are only using variables to store the frequencies, and current elements,
Hence the space complexity is O(1).
All tags
Sort by
Interview problems
Java || Simple Code || HashMap || O(n)
import java.util.HashMap;
public class Solution {
public static int majorityElement(int []v) {
// Write your code here
HashMap<Integer,Integer> map = new HashMap<>();
int max = 0, val = v[0];
for(int i=0;i<v.length;i++){
map.put(v[i],map.getOrDefault(v[i], 0)+1);
int value = map.get(v[i]);
if(map.get(v[i])>max){
max = map.get(v[i]);
val = v[i];
if(max > v.length/2) return val;
}
}
return val;
}
}
Interview problems
Using Boyer Moore Voting Algorithm O(1) space.
import java.util.HashMap;
public class Solution {
public static int majorityElement(int []v) {
// Write your code here
// 1. Using HashMap
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<v.length; i++) {
map.put(v[i], map.getOrDefault(v[i], 0) + 1);
}
for (HashMap.Entry<Integer, Integer> entry: map.entrySet()) {
if (entry.getValue() > v.length/2) {
return entry.getKey();
}
}
return -1;
// Using Boyer Moore Voting Algorithm
int count = 0;
int candidate = 0;
for (int i=0; i<v.length; i++) {
if (count == 0) {
candidate = v[i];
}
if (v[i] == candidate) {
count++;
}else {
count--;
}
}
return candidate;
}
}
Interview problems
Using HashMap
import java.util.HashMap;
public class Solution {
public static int majorityElement(int []v) {
// Write your code here
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<v.length; i++) {
map.put(v[i], map.getOrDefault(v[i], 0) + 1);
}
for (HashMap.Entry<Integer, Integer> entry: map.entrySet()) {
if (entry.getValue() > v.length/2) {
return entry.getKey();
}
}
return -1;
}
}
Interview problems
C++ || Very EASY || O(N) 🔥
#include <vector>
using namespace std;
int majorityElement(vector<int> v) {
int candidate = -1;
int count = 0;
int n = v.size();
// Step 1: Find a candidate for majority element
for (int i = 0; i < n; i++) {
if (count == 0) {
candidate = v[i];
count = 1;
} else if (v[i] == candidate) {
count++;
} else {
count--;
}
}
// Step 2: Verify the candidate
count = 0;
for (int i = 0; i < n; i++) {
if (v[i] == candidate) {
count++;
}
}
if (count > n / 2) {
return candidate;
}
return -1;
}
Interview problems
By Moore's Voting algorithm-optimal solution
int majorityElement(vector<int> v) {
// Write your code here
int count=0;
int ele;
for(int i=0;i<v.size();i++){
if(count==0){
count=1; //for new element
ele=v[i];
}
else if(v[i]==ele) count++; //if element is found then increment
else count--; //if element is not found decrement
}
int count1=0;
for(int i=0;i<v.size();i++){
if(v[i]==ele) count1++; //count the freq of element we got
}
if(count1>(v.size()/2)){ //if greter than N/2 return it.
return ele;
}
return -1;
}
Interview problems
Moore's voting algorithms Optimal solutions
def majorityElement(arr: [int]) -> int:
# Write your code here
n = len(arr)
cnt = 0 # Count
el = None # Element
# Applying the algorithm
for i in range(n):
if cnt == 0:
cnt = 1
el = arr[i]
elif el == arr[i]:
cnt += 1
else:
cnt -= 1
# Checking if the stored element is the majority element
cnt1 = 0
for i in range(n):
if arr[i] == el:
cnt1 += 1
if cnt1 > (n / 2):
return el
return -1Interview problems
BY MAP in c++
#include<bits/stdc++.h>
int majorityElement(vector<int> v) {
// Write your code here
int n = v.size();
map<int,int>count ;
for(int i =0; i<n; i++){
count[v[i]]++;
}
for(auto i : count){
//alternate map
if(i.second > (n/2)){
return i.first;
}
}
return -1;
}
Interview problems
Java Solution
//Using HashMap
public class Solution {
public static int majorityElement(int []v) {
int n=v.length;
// Write your code here
HashMap<Integer,Integer> map =new HashMap<>();
for(int i:v){
map.put(i,map.getOrDefault(i,0)+1);
}
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue()>n/2){
return entry.getKey();
}
}
return 0;
}
}
//Moore's Voting algo
public class Solution {
public static int majorityElement(int []v) {
int n=v.length;
int count=0;
int el=0;
for(int i=0;i<n;i++){
if(count==0){
count=1;
el=v[i];
}else if(v[i]==el){
count++;
}else count--;
}
return el;
}
}
Interview problems
Majority Element
int majorityElement(vector<int> v) {
// Write your code here
int cnt = 0;
int ele;
for(int i=0; i<v.size(); i++){
if(cnt == 0){
cnt = 1;
ele = v[i];
}else if(v[i] == ele){
cnt++;
}else{
cnt--;
}
}
int cnt1 = 0;
for(int i=0; i<v.size(); i++){
if(v[i] == ele)
cnt1++;
}
if(cnt1 > (v.size()/2))
return ele;
return -1;
}
Interview problems
java optimized code ✅✅✅✅✅
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static int majorityElement(int[] v) {
// size of the given array:
int n = v.length;
// declaring a map to store the occurrences of each element:
HashMap<Integer, Integer> mpp = new HashMap<>();
// storing the elements with their occurrences:
for (int i = 0; i < n; i++) {
int value = mpp.getOrDefault(v[i], 0);
mpp.put(v[i], value + 1);
}
// searching for the majority element:
for (Map.Entry<Integer, Integer> entry : mpp.entrySet()) {
if (entry.getValue() > (n / 2)) {
return entry.getKey();
}
}
// returning -1 if no majority element is found:
return -1;
}
}
