Majority Vote | GFG POTD 3rd Oct 2024 | JAVA | C++

[@mayuridubey6139]

Why can't we do this with a hashmap

[@ajinkyajain2302]

Because it will take O(N) extra space and the expected space complexity is O(1).

[@ajinkyajain2302]

C++ Code :
vector findMajority(vector& nums) {
int num1 = INT_MAX, num2 = INT_MAX;
int freq1 = 0, freq2 = 0;
// First pass: Find potential candidates for majority elements
for(int num : nums) {
if(num1 == num) {
freq1++;
}
else if(num2 == num) {
freq2++;
}
else if(freq1 == 0) {
num1 = num;
freq1 = 1;
}
else if(freq2 == 0) {
num2 = num;
freq2 = 1;
}
else {
freq1--;
freq2--;
}
}
// Second pass: Count occurrences of the candidates
freq1 = 0;
freq2 = 0;
for(int num : nums) {
if(num == num1) {
freq1++;
}
else if(num == num2) {
freq2++;
}
}
// Add the candidates to the result if they appear more than n/3 times
vector res;
if(freq1 > nums.size() / 3) {
res.push_back(num1);
}
if(freq2 > nums.size() / 3) {
res.push_back(num2);
}
// If no majority elements are found, return -1
if(res.empty()) {
res.push_back(-1);
}
return res;
}

[@ajinkyajain2302]

JAVA Code :
public List findMajority(List nums) {
// Your code goes here.
int num1 = Integer.MAX_VALUE;
int num2 = Integer.MAX_VALUE;
int f1 = 0;
int f2 = 0;
for(int num : nums){
if(num == num1){
++f1;
}
else if(num == num2){
++f2;
}
else if(f1 == 0){
num1 = num;
f1++;
}
else if(f2 == 0){
num2 = num;
f2++;
}
else{
f1--;
f2--;
}
}
f1 = 0;
f2 = 0;
for(int num : nums){
if(num == num1){
++f1;
}
if(num == num2){
++f2;
}
}
List res =new ArrayList();
int n = nums.size();
if(f1 > n / 3){
res.add(num1);
}
if(f2 > n / 3){
res.add(num2);
}
if(res.isEmpty()){
res.add(-1);
}
return res;
}