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;
}