FilesExpand file tree

 main

/

Program124.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

45 lines (33 loc) · 1.53 KB

 main

/

Program124.java

Top

File metadata and controls

• Code
• Blame

45 lines (33 loc) · 1.53 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

import java.util.*;

public class Program124 {

//Count Distinct Elements in Every Window of Size K

public static List<Integer> countDistinctElements(int[] arr, int k) {

List<Integer> result = new ArrayList<>(); // To store result for each window

Map<Integer, Integer> freqMap = new HashMap<>(); // To store frequency of elements in window

// Initialize first window

for (int i = 0; i < k; i++) {

freqMap.put(arr[i], freqMap.getOrDefault(arr[i], 0) + 1); // Count frequency

}

result.add(freqMap.size()); // Add count of distinct elements in first window

// Slide the window

for (int i = k; i < arr.length; i++) {

int toRemove = arr[i - k]; // Element going out of window

// Decrease its frequency

freqMap.put(toRemove, freqMap.get(toRemove) - 1);

// Remove it completely if frequency is 0

if (freqMap.get(toRemove) == 0) {

freqMap.remove(toRemove);

}

// Add new element coming into the window

freqMap.put(arr[i], freqMap.getOrDefault(arr[i], 0) + 1);

// Add current distinct count

result.add(freqMap.size());

}

return result;

}

public static void main(String[] args) {

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

int k = 4;

System.out.println("Distinct counts in each window of size " + k + ": " + countDistinctElements(arr, k));

}

}