Count Distinct Elements in Every Window of Size K in Python

Program Explanation

This program counts the number of distinct elements in each window of size k in a given list of integers. It uses a sliding window approach combined with a hash map to keep track of element counts efficiently.

Program Structure

• Function Definition: The main functionality is encapsulated in the function count_distinct_in_window(arr, k).

Parameters:

• arr: A list of integers in which to count distinct elements.
• k: The size of the window to consider.

Logic:

• Use a hash map (dictionary) to store the count of each element in the current window.
• Iterate through the array using a sliding window technique to update counts and track distinct elements.
• Output the count of distinct elements for each window.

Python Code

def count_distinct_in_window(arr, k):
    """
    Count distinct elements in every window of size k in the array.

    Parameters:
    arr (list): List of integers.
    k (int): Size of the sliding window.

    Returns:
    list: A list containing the count of distinct elements for each window.
    """
    if k <=…