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 <= 0 or k > len(arr):
        return []

    # Dictionary to store the count of elements in the current window
    count_map = {}
    distinct_counts = []

    # Initialize the first window
    for i in range(k):
        count_map[arr[i]] = count_map.get(arr[i], 0) + 1

    # The number of distinct elements in the first window
    distinct_counts.append(len(count_map))

    # Slide the window over the array
    for i in range(k, len(arr)):
        # Remove the element going out of the window
        outgoing_element = arr[i - k]
        count_map[outgoing_element] -= 1
        if count_map[outgoing_element] == 0:
            del count_map[outgoing_element]  # Remove it if its count is zero

        # Add the new element coming into the window
        incoming_element = arr[i]
        count_map[incoming_element] = count_map.get(incoming_element, 0) + 1

        # Add the number of distinct elements in the current window
        distinct_counts.append(len(count_map))

    return distinct_counts

# Example usage
arr = [1, 2, 1, 3, 4, 2, 3]
k = 3
print(count_distinct_in_window(arr, k))

How to Use

To use this program, simply call the function count_distinct_in_window with your array and the desired window size k. The function will return a list with the counts of distinct elements for each window.

Example

For the input array [1, 2, 1, 3, 4, 2, 3] with window size k = 3, the output will be:

[2, 3, 3, 2]

Conclusion

This program efficiently counts distinct elements in every window of size k using a sliding window approach, ensuring optimal performance even for larger lists.