# Easy to understand java solution

• ``````public class Solution {
public List<Integer> majorityElement(int[] nums) {
if(nums.length==0)return res;
//get candidates
int element1=0, element2=0;
boolean e=false; //used for edge case where all the numbers in the array are the same number.
int count1=0, count2=0;
for(int i=0; i<nums.length; i++){
if(count1==0){
element1=nums[i];
count1++;
}
else if(nums[i]==element1)count1++;
else if(count2==0){
e=true;
element2=nums[i];
count2++;
}
else if(nums[i]==element2)count2++;
else{
count1--;
count2--;
}
}
count1=0; count2=0;
for(int i=0; i<nums.length; i++){
if(nums[i]==element1)count1++;
else if(e&&nums[i]==element2)count2++;
}
//check if candidates have majority vote
return res;
}
}``````

• Nice solution using extension of Boyer-Moore algorithm (https://en.wikipedia.org/wiki/Boyer-Moore_Majority_Vote_Algorithm). However, I don't think there is a need of extra boolean variable e. The edge case mentioned will be handled without it as well.

Below is a generalized version of this problem. Instead of n/3, it works for n/k for a given k >= 2. So, given an array and k, it gives list of integers who occur more than n/k times in the array.

``````List<Integer> generalizedBoyerMoore(int[] nums, int k) {
Integer [] candidate = new Integer[k-1];
int[] count = new int[k-1];
int freq = nums.length / k;
for(int vote : nums) {
int i;
for(i = 0; i < count.length; i++) {
if(count[i] == 0 || vote == candidate[i]) {
count[i]++;
candidate[i] = vote;
break;
}
}
if(i == count.length) {
for(int j = 0; j < count.length; j++)
count[j]--;
}
}

List<Integer> possible = new ArrayList<Integer>();
for(int i = 0; i < candidate.length; i++) {
if(candidate[i] != null)
else break;
}
count = new int[possible.size()];

for(int vote : nums) {
for(int i = 0; i < possible.size(); i++) {
if(vote == possible.get(i)) {
count[i]++;
break;
}
}
}

List<Integer> result = new ArrayList<Integer>();

for(int i = 0; i < count.length; i++)
if(count[i] > freq)