Java - Count Distinct Elements in Every Window of Size K

Problem Statement

Given an array arr[] of size N and an integer K, find the count of distinct elements in every window of size K.

Example 1:

Input: arr[] = {1, 2, 1, 3, 4, 2, 3}, K = 4  

Output: [3, 4, 4, 3]

Explanation

Window [1, 2, 1, 3] → Distinct Count = 3 → {1, 2, 3}

Window [2, 1, 3, 4] → Distinct Count = 4 → {1, 2, 3, 4}

Window [1, 3, 4, 2] → Distinct Count = 4 → {1, 3, 4, 2}

Window [3, 4, 2, 3] → Distinct Count = 3 → {3, 4, 2}

Approach 1: Brute Force (O(K × N))

Traverse every window of size K.

Use a HashSet to count distinct elements.

Code Implementation

import java.util.*;

public class DistinctElementsBruteForce {

    public static List<Integer> countDistinct(int[] arr, int K) {

        List<Integer> result = new ArrayList<>();       

        for (int i = 0; i <= arr.length - K; i++) {

            Set<Integer> set = new HashSet<>();

            for (int j = i; j < i + K; j++) {

                set.add(arr[j]); // Add elements to HashSet

            }

            result.add(set.size()); // Count distinct elements

        }

        return result;

    }

    public static void main(String[] args) {

        int[] arr = {1, 2, 1, 3, 4, 2, 3};

        int K = 4;

        System.out.println(countDistinct(arr, K));  

        // Output: [3, 4, 4, 3]

    }

}

Time Complexity Analysis

Step Complexity

Outer Loop (N-K+1 windows) O(N-K+1)

Inner Loop (Insert elements into HashSet) O(K)

Total Complexity O(K × (N-K+1)) ≈ O(NK)