Distinct Numbers in Each Subarray

class Solution {
public:
    vector<int> uniqueNumbers(vector<int>& data, int windowSize) {
        int highestValue = 0;
        for (int value : data) {
            if (value > highestValue) {
                highestValue = value;
            }
        }

        vector<int> frequency(highestValue + 1, 0);
        int uniqueCount = 0;
        vector<int> result;

        for (int index = 0; index < data.size(); index++) {
            frequency[data[index]]++;
            if (frequency[data[index]] == 1) {
                uniqueCount++;
            }

            if (index >= windowSize) {
                frequency[data[index - windowSize]]--;
                if (frequency[data[index - windowSize]] == 0) {
                    uniqueCount--;
                }
            }

            if (index + 1 >= windowSize) {
                result.push_back(uniqueCount);
            }
        }

        return result;
    }
};

This solution addresses the problem of finding the number of distinct numbers in each subarray of a given size within an array. Here's a concise breakdown of the C++ implementation to achieve this:

• Initialize the maximum value found in the array. This helps in setting up a frequency array where indices represent numbers from the input array.
• Create a frequency array to keep track of the count of each number within the current window of specified size.
• Use a variable, uniqueCount, to maintain the count of unique numbers in the current window.
• Iterate through the input data, adjusting the frequency of each number and updating the uniqueCount accordingly:
  • Increase the frequency of the current element. If it's the first occurrence (frequency becomes 1), increment uniqueCount.
  • For elements outside the current window (i.e., when the index is greater than or equal to the window size), decrease their frequency. If the frequency drops to zero, decrement uniqueCount.
• Append the uniqueCount to the result list once the first window is fully processed (i.e., when the current index plus one is greater than or equal to the window size).
• Continue this process until the end of the array is reached, then return the resultant list of unique counts for each window.

This method ensures efficient tracking and updating of unique elements in sliding windows across the array, leveraging direct access features of the frequency array indexed by the actual values of the elements. This approach achieves the desired functionality with a clear and structured flow.

class Solution {

    public int[] calculateDistinct(int[] elements, int windowSize) {
        // Calculate the largest number in the elements array
        int highestValue = 0;
        for (int element : elements) {
            if (element > highestValue) {
                highestValue = element;
            }
        }

        // Initialize the frequency array for the maximum value found
        int[] frequency = new int[highestValue + 1];
        int uniqueCount = 0;
        int[] result = new int[elements.length - windowSize + 1];
        int resultIndex = 0;

        for (int idx = 0; idx < elements.length; idx++) {
            // Increment frequency of the current element
            frequency[elements[idx]]++;
            if (frequency[elements[idx]] == 1) {
                uniqueCount++;
            }

            // Decrement frequency of the element that moves out of the window
            if (idx >= windowSize) {
                frequency[elements[idx - windowSize]]--;
                if (frequency[elements[idx - windowSize]] == 0) {
                    uniqueCount--;
                }
            }

            // Record the count of distinct elements when the window is full
            if (idx + 1 >= windowSize) {
                result[resultIndex++] = uniqueCount;
            }
        }

        return result;
    }
}

This Java-based solution intends to determine the number of distinct numbers in each subarray of a specified size, utilizing sliding window technique. Here's a detailed explanation of the given code:

• Initialization and Finding Highest Value:

  • Start by identifying the maximum value in the input array, elements. This maximal value defines the necessary size for the frequency array, which tracks how many times each number appears in the current window of numbers.

• Setup for Sliding Window:

  • Utilize a frequency array indexed by the numbers found in elements to count occurrences efficiently.
  • Introduce two key variables: uniqueCount to keep the number of distinct elements in the current window and result to store the number of distinct elements for each window position across the elements array.

• Sliding Window Execution:

  • Iterate through each element in the input array. At each position, modify the frequency of the current element (increment given the element has just been added to the window).
  • Check and update the unique count: if you encounter a number for the first time, increase the uniqueCount.
  • Adjust the window by reducing the frequency of the element that exits the window as the index surpasses the window size. Accordingly, adjust the uniqueCount if an element count drops to zero.
  • Capture the count of distinct elements in result whenever the window completes a shift (reaches its specified size), then move the window one element forward.

• Final Output:

  • Once the iteration completes, yielding at each step the count of unique numbers for each respective window, return the result array containing these counts.

This solution efficiently builds upon frequency counting and window sliding combined with conditional checks to keep track of distinct numbers as the window moves across the original array. The granularity of iterations and conditional logic ensures that the solution caters to the dynamic changes in frequency resulting from the window's shift, making it ideal for problems involving contiguous subarray analysis within a larger dataset.

class Solution:
    def uniqueCount(self, elements: List[int], window: int) -> List[int]:
        highest_value = max(elements)
        count = [0] * (highest_value + 1)
        unique = 0
        result = []

        for index in range(len(elements)):
            count[elements[index]] += 1
            if count[elements[index]] == 1:
                unique += 1
            
            if index >= window:
                count[elements[index - window]] -= 1
                if count[elements[index - window]] == 0:
                    unique -= 1
            
            if index + 1 >= window:
                result.append(unique)

        return result

The provided Python code defines a function uniqueCount that calculates the number of distinct numbers in each subarray of a given list. The function accepts two parameters: elements, a list of integers, and window, an integer representing the size of the subarray (window size).

To determine the number and list of distinct numbers in each sliding window of the given list:

• Initialize highest_value to hold the maximum integer value in the elements list for defining the size of the counting list.
• Create a list count initialized with zeros to keep track of each number's frequency in the current subarray.
• Initialize unique to zero, counting the number of unique numbers in the current window.
• Initialize an empty list result to store the number of distinct integers for each window when it fully traverses the elements.

The algorithm employs a sliding window technique with the help of index index iterating over each element in the elements list:

• Update the frequency of the current element and adjust the unique count accordingly.
• If the index exceeds the window size, decrement the count of the element that falls out of the current window and update the unique count if that element’s frequency in count drops to zero.
• Once the window is sufficiently filled (i.e., index + 1 >= window), append the current unique count to result.

The function returns the result list after the loop, which contains the number of distinct numbers for each sliding window of size window in the elements list.