Incorrect test case: 1838. Frequency of the Most Frequent Element

LeetCode Username

avinashdhinwa

Problem number, title, and link

Frequency of the Most Frequent Element https://leetcode.com/problems/frequency-of-the-most-frequent-element/

Category of the bug

[ ] Problem description
[ ] Solved examples
[ ] Problem constraints
[ ] Problem hints
[ ] Incorrect or missing "Related Topics"
[x] Incorrect test Case (Output of test case is incorrect as per the problem statement)
[ ] Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
[ ] Editorial
[ ] Programming language support

Description of the bug

Incorrect test case, have added more information in the Expected Behaviour Section.

A similar bug was reported 2 years ago as well but closed without any actions I guess: https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/5395.

Language used for code

Golang

Code used for Submit/Run operation

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)

    left, leftRightSum, totalSum := 0, 0, 0
    ans := 1

    for i := 1; i < len(nums); i++ {
        // fmt.Printf("\n")
        newDiff := (nums[i] - nums[i-1])
        leftRightSum = leftRightSum + newDiff
        totalSum = totalSum + leftRightSum
        // fmt.Printf("left: %d, i:%d \n", left, i)
        // fmt.Printf("newDiff: %d, leftRightSum: %d, totalSum:%d \n", newDiff, leftRightSum, totalSum)
        for ; left < i && totalSum > k ; left++ {
            leftDiff := (nums[left+1] - nums[left])
            leftRightSum = leftRightSum - leftDiff
            totalSum = totalSum - (i-left)*leftDiff
            // fmt.Printf("\t left: %d, i:%d \n", left, i)
            // fmt.Printf("\t leftDiff: %d, leftRightSum: %d, totalSum:%d \n", leftDiff, leftRightSum, totalSum)
        }
        ans = max(ans, i - left + 1)
        // fmt.Printf("length: %d with totalSum: %d, opsTakenToReachLastNum: %d, arr: %v \n", ans, totalSum, findOpsTakenToReachLastNum(nums[left:i+1]), nums[left:i+1])
    }

    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func findOpsTakenToReachLastNum(nums []int) int {
    ans := 0
    lastIndex := len(nums)
    for i := 1; i < lastIndex; i++ {
        ans = ans + (nums[i] - nums[0])
    }
    return ans
}

Expected behavior

For the below test case with nums = [9930,9923,9983,9997,9934,9952,9945,9914,9985,9982,9970,9932,9985,9902,9975,9990,9922,9990,9994,9937,9996,9964,9943,9963,9911,9925,9935,9945,9933,9916,9930,9938,10000,9916,9911,9959,9957,9907,9913,9916,9993,9930,9975,9924,9988,9923,9910,9925,9977,9981,9927,9930,9927,9925,9923,9904,9928,9928,9986,9903,9985,9954,9938,9911,9952,9974,9926,9920,9972,9983,9973,9917,9995,9973,9977,9947,9936,9975,9954,9932,9964,9972,9935,9946,9966] and k = 3056

We can set all the numbers in below array to 9913 with just 2957 operations (which is still less than 3056). And the length of this array is 78 (which is greater than 73, expected answer for this test case)

[9913 9914 9916 9916 9916 9917 9920 9922 9923 9923 9923 9924 9925 9925 9925 9926 9927 9927 9928 9928 9930 9930 9930 9930 9932 9932 9933 9934 9935 9935 9936 9937 9938 9938 9943 9945 9945 9946 9947 9952 9952 9954 9954 9957 9959 9963 9964 9964 9966 9970 9972 9972 9973 9973 9974 9975 9975 9975 9977 9977 9981 9982 9983 9983 9985 9985 9985 9986 9988 9990 9990 9993 9994 9995 9996 9997]

LeetCode-Feedback / LeetCode-Feedback