Time Complexity of Inner Loop of sliding window algorithm

Question

I am looking at a 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!

trincot · Accepted Answer · 2024-05-20 19:33:46Z

0

why the loops' combined runtime is O(n) instead of O(n^2).

The value of l is the key to understanding this. It represents the total number of iterations that the inner loop will make, so over the course of the complete execution of the algorithm.

As l will not exceed the size of the input, the total number of executions of the inner loop body will not exceed 𝑛.

That's why it doesn't increase the total complexity from O(𝑛) to O(𝑛²). It remains O(𝑛).

And so it is true that the sort operation is the bottleneck in terms of complexity.

answered May 20, 2024 at 19:33

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

enigma312 Over a year ago

This actually made a lot of sense. So basically the inner loop iterates a TOTAL of n times not n times for each iteration of r.

trincot Over a year ago

Yes, that is the key take away!

Collectives™ on Stack Overflow

Time Complexity of Inner Loop of sliding window algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related