I am looking at 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 have this sliding window approach that solves it:

def maxFrequency(self, nums: List[int], k: int) -> int:
    nums.sort()
    res, curSum = 0, 0
    l = 0
    for r in range(len(nums)):
        total = nums[r] * (r - l + 1)  # the goal
        curSum += nums[r]  # what we currently have

        # check if we have enough operations to reach our goal
        while total - curSum > k:
            # remove L until we have valid subsequence
            curSum -= nums[l]
            l += 1
            total = nums[r] * (r - l + 1)
     
        res = max(res, r - l + 1)
    
    return res

On discussion boards it is claimed that this approach has a runtime of O(nlogn) since it is bottlenecked by the sorting of the nums array, but I do not understand the calculation.

I assumed that the for loop had a runtime of O(n) and that the inner while loop had a worst-case runtime of O(n) also. As a result, wouldn’t the time complexity of the program be:

O(nlogn) + [O(n) * O(n)] = O(nlogn) + O(n^2) = O(n^2)?

My question is why the loops’ combined runtime is O(n) instead of O(n^2). I would really appreciate if someone could help explain this idea to me!