Program in Go

package main

import (
    "fmt"
    "map"
)

// Function to count distinct elements in every window of size k
func countDistinct(arr []int, k int) []int {
    // Map to store the count of elements in the current window
    elementCount := make(map[int]int)
    distinctCounts := []int{}

    // Initializing the first window
    for i := 0; i < k; i++ {
        elementCount[arr[i]]++
    }
    // Count of distinct elements in the first window
    distinctCounts = append(distinctCounts, len(elementCount))

    // Slide the window from start to end of the array
    for i := k; i < len(arr); i++ {
        // Remove the element going out of the window
        elementCount[arr[i-k]]--
        if elementCount[arr[i-k]] == 0 {
            delete(elementCount, arr[i-k])
        }
        
        // Add the new element coming into the window
        elementCount[arr[i]]++

        // Count of distinct elements in the current window
        distinctCounts = append(distinctCounts, len(elementCount))
    }

    return distinctCounts
}

func main() {
    arr := []int{1, 2, 1, 3, 4, 2, 3}
    k := 3
    result := countDistinct(arr, k)
    fmt.Println("Count of distinct elements in every window of size", k, ":", result)
}

Program Explanation

The program defines a function countDistinct that takes an array of integers and a window size k. It counts the distinct elements in every sliding window of size k as it traverses the array.

Program Structure

• Imports: The program imports the fmt package for formatted I/O and the map package for using a hash map to count elements.
• Function countDistinct:
  • Initializes a map elementCount to keep track of the counts of each element in the current window.
  • Loops through the first k elements to populate the map and counts the distinct elements.
  • Slides the window across the array: for each new element, it decrements the count of the element that is sliding out of the window and increments the count for the new element.
  • If an element’s count goes to zero, it is removed from the map.
  • Counts the distinct elements after updating the map for each window and stores the results in distinctCounts.
• Main Function:
  • Defines an example array and a window size k.
  • Calls countDistinct and prints the results.

Conclusion

This Go program efficiently counts the distinct elements in every sliding window of size k using a hash map for tracking counts, providing a time complexity of O(n) where n is the size of the array.