MajorityVote.java

//GFG POTD Date: 03/09/24

// You are given an array of integer nums[] where each number represents a vote to a candidate. Return the candidates that have votes greater than one-third of the total votes, If there's not a majority vote, return -1. 

// Examples:
// Input: nums = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]
// Output: [5, 6]
// Explanation: 5 and 6 occur more n/3 times.

// Input: nums = [1, 2, 3, 4, 5]
// Output: [-1]
// Explanation: no candidate occur more than n/3 times.
import java.util.*;
class MajorityVote {
    static List<Integer> findMajority(List<Integer> nums) {
    int count1 = 0, count2 = 0, candidate1 = 0, candidate2 = 0;

    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }
    
    List<Integer> result = new ArrayList<>();
    int n = nums.size();
    
    if (count1 > n / 3) result.add(candidate1);
    if (count2 > n / 3) result.add(candidate2);
    
    if (result.isEmpty()) {
        result.add(-1);
    }
    
    return result;
    }


    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        nums.add(5);

        List<Integer> result = findMajority(nums);
        System.out.println(result);
    }
}