# Boyer-Moore Majority Volting Algorithm Generalized to k (appear more than n/k times)

• ``````vector<int> majorityElement(vector<int>&nums, int k) {
vector<int> result;
if (k < 2) return result;
// there are at most k-1 candidates
vector<int> candidates(k-1, 0);
vector<int> count(k-1, 0);

// initialize candidates array with different values
// otherwise, the all zeros nums vector will fail
for (int i = 0; i < k-1; ++i)
candidates[i] = i;

// first loop, if one candidate appears more than n/k times,
// the maximal number of times it can be offset by other candidates is n/k
for (int num : nums) {
bool found = false;
for (int j = 0; j < k-1; ++j) {
if (num == candidates[j]) {
++count[j];
found = true;
break;
}
}

if (!found) {
for (int j = 0; j < k-1; ++j) {
if (count[j] == 0) {
candidates[j] = num;
++count[j];
found = true;
break;
}
}
}
if (!found) {
for (int j = 0; j < k-1; ++j) {
--count[j];
}
}
}

// second loop: find candidates that appear more than n/k times
count.assign(k-1, 0);
for (int num : nums) {
for (int j = 0; j < k-1; ++j) {
if (candidates[j] == num)
++count[j];
}
}

for (int j = 0; j < k-1; ++j) {
if (count[j] > nums.size()/k)
result.push_back(candidates[j]);
}
return result;
}``````

• This is not the constant space solution as asked in problem

• because it's `Generalized`

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.