#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sliding-window/at-most-k-helper-function

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sliding-window/at-most-k-helper-function

Repovive

At Most K - Helper Function - Sliding Window | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

At Most K - Helper Function

Helper implementation

function atMost(nums, k):
    count = empty map
    left = 0
    result = 0

    for right from 0 to nums.length - 1:
        count[nums[right]] = count.get(nums[right], 0) + 1

        while count.size > k:
            count[nums[left]] = count[nums[left]] - 1
            if count[nums[left]] == 0:
                count.remove(nums[left])
            left = left + 1

        result = result + (right - left + 1)

    return result

Time: $O(n)$ . Space: $O(k)$ .