I am trying LeetCode problem 1838. Frequency of the Most Frequent Element:

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

I am getting a Wrong Answer error for a specific test case.

My code

int checkfreq(vector<int>nums,int k,int i)
{
    //int sz=nums.size();
    int counter=0;
    //int i=sz-1;
    int el=nums[i];
    while(k!=0 && i>0)
    {
        --i;
        while(nums[i]!=el && k>0 && i>=0)
        {
              nums[i];
            --k;
        }
    }
    counter=count(nums.begin(),nums.end(),el);
    return counter;
}


class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        vector<int> nums2=nums;
        auto distinct=unique(nums2.begin(),nums2.end());
        nums2.resize(distance(nums2.begin(),distinct));
        int xx=nums.size()-1;
        int counter=checkfreq(nums,k,xx);
        for(int i=nums2.size()-2;i>=0;--i)
        {
            --xx;
            int temp=checkfreq(nums,k,xx);
            if(temp>counter)
                counter=temp;
        }
   
        return counter;
        
    }
};

Failing test case

Input

nums = [9968,9934,9996,9928,9934,9906,9971,9980,9931,9970,9928,9973,9930,9992,9930,9920,9927,9951,9939,9915,9963,9955,9955,9955,9933,9926,9987,9912,9942,9961,9988,9966,9906,9992,9938,9941,9987,9917,10000,9919,9945,9953,9994,9913,9983,9967,9996,9962,9982,9946,9924,9982,9910,9930,9990,9903,9987,9977,9927,9922,9970,9978,9925,9950,9988,9980,9991,9997,9920,9910,9957,9938,9928,9944,9995,9905,9937,9946,9953,9909,9979,9961,9986,9979,9996,9912,9906,9968,9926,10000,9922,9943,9982,9917,9920,9952,9908,10000,9914,9979,9932,9918,9996,9923,9929,9997,9901,9955,9976,9959,9995,9948,9994,9996,9939,9977,9977,9901,9939,9953,9902,9926,9993,9926,9906,9914,9911,9901,9912,9990,9922,9911,9907,9901,9998,9941,9950,9985,9935,9928,9909,9929,9963,9997,9977,9997,9938,9933,9925,9907,9976,9921,9957,9931,9925,9979,9935,9990,9910,9938,9947,9969,9989,9976,9900,9910,9967,9951,9984,9979,9916,9978,9961,9986,9945,9976,9980,9921,9975,9999,9922]
k = 1524

Output

Expected: 81

My code returns: 79

I tried to solve as many cases as I could. I realise this is a bruteforce approach, but don't understand why my code is giving the wrong answer.

My approach is to convert numbers from last into the specified number. I need to check these as we have to count how many maximum numbers we can convert. Then this is repeated for every number till second last number. This is basically what I was thinking while writing this code.

CodePudding user response：

The reason for the different output is that your xx index is only decreased one unit at each iteration of the i loop. But that loop is iterating for the number of unique elements, while xx is an index in the original vector. When there are many duplicates, that means xx is coming nowhere near the start of the vector and so it misses opportunities there.

You could fix that problem by replacing:

--xx;

...with:

--xx;
while (xx >= 0 && nums[xx] == nums[xx 1]) --xx;
if (xx < 0) break;

That will solve the issue you raise. You can also drop the unique call, and the distinct, nums2 and i variables. The outer loop could just check that xx > 0.

Efficiency is your next problem

Your algorithm is not as efficient as needed, and other tests with huge input data will time out.

Hint 1: checkfreq's inner loop is incrementing nums[i] one unit at a time. Do you see a way to have it increase with a larger amount, so to avoid that inner loop?

Hint 2 (harder): checkfreq is often incrementing the same value in different calls -- even more so when k is large and the section of the vector that can be incremented is large. Can you think of a way to avoid that checkfreq needs to redo that much work in subsequent calls, and can only concentrate on what is different compared to what it had to calculate in the previous call?